1
/* NSC -- new Scala compiler
2
* Copyright 2005-2013 LAMP/EPFL
3
* @author Martin Odersky
9
import scala.collection.{ mutable, immutable, generic }
10
import generic.Clearable
11
import scala.ref.WeakReference
12
import mutable.ListBuffer
14
import scala.util.control.ControlThrowable
15
import scala.annotation.tailrec
16
import util.Statistics
17
import scala.runtime.ObjectRef
18
import util.ThreeValues._
20
/* A standard type pattern match:
25
case BoundedWildcardType(bounds) =>
31
case SuperType(thistpe, supertpe) =>
33
case SingleType(pre, sym) =>
35
case ConstantType(value) =>
37
case TypeRef(pre, sym, args) =>
39
// Outer.this.C would be represented as TypeRef(ThisType(Outer), C, List())
40
case RefinedType(parents, defs) =>
41
// parent1 with ... with parentn { defs }
42
case ExistentialType(tparams, result) =>
43
// result forSome { tparams }
44
case AnnotatedType(annots, tp, selfsym) =>
47
// the following are non-value types; you cannot write them down in Scala source.
49
case TypeBounds(lo, hi) =>
51
case ClassInfoType(parents, defs, clazz) =>
52
// same as RefinedType except as body of class
53
case MethodType(paramtypes, result) =>
55
// For instance def m(): T is represented as MethodType(List(), T)
56
case NullaryMethodType(result) => // eliminated by uncurry
57
// an eval-by-name type
58
// For instance def m: T is represented as NullaryMethodType(T)
59
case PolyType(tparams, result) =>
60
// [tparams]result where result is a (Nullary)MethodType or ClassInfoType
62
// The remaining types are not used after phase `typer`.
63
case OverloadedType(pre, tparams, alts) =>
64
// all alternatives of an overloaded ident
65
case AntiPolyType(pre, targs) =>
66
// rarely used, disappears when combined with a PolyType
67
case TypeVar(inst, constr) =>
69
// Replace occurrences of type parameters with type vars, where
70
// inst is the instantiation and constr is a list of bounds.
71
case DeBruijnIndex(level, index, args)
72
// for dependent method types: a type referring to a method parameter.
73
case ErasedValueType(tref)
74
// only used during erasure of derived value classes.
77
trait Types extends api.Types { self: SymbolTable =>
81
private var explainSwitch = false
82
private final val emptySymbolSet = immutable.Set.empty[Symbol]
84
private final val LogPendingSubTypesThreshold = 50
85
private final val LogPendingBaseTypesThreshold = 50
86
private final val LogVolatileThreshold = 50
88
/** A don't care value for the depth parameter in lubs/glbs and related operations. */
89
private final val AnyDepth = -3
91
/** Decrement depth unless it is a don't care. */
92
private final def decr(depth: Int) = if (depth == AnyDepth) AnyDepth else depth - 1
94
private final val printLubs = sys.props contains "scalac.debug.lub"
95
private final val traceTypeVars = sys.props contains "scalac.debug.tvar"
96
/** In case anyone wants to turn off lub verification without reverting anything. */
97
private final val verifyLubs = true
98
/** In case anyone wants to turn off type parameter bounds being used
99
* to seed type constraints.
101
private final val propagateParameterBoundsToTypeVars = sys.props contains "scalac.debug.prop-constraints"
103
protected val enableTypeVarExperimentals = settings.Xexperimental.value
105
/** Empty immutable maps to avoid allocations. */
106
private val emptySymMap = immutable.Map[Symbol, Symbol]()
107
private val emptySymCount = immutable.Map[Symbol, Int]()
109
/** The current skolemization level, needed for the algorithms
110
* in isSameType, isSubType that do constraint solving under a prefix.
112
var skolemizationLevel = 0
114
/** A log of type variable with their original constraints. Used in order
115
* to undo constraints in the case of isSubType/isSameType failure.
117
lazy val undoLog = newUndoLog
119
protected def newUndoLog = new UndoLog
121
class UndoLog extends Clearable {
122
private type UndoPairs = List[(TypeVar, TypeConstraint)]
123
//OPT this method is public so we can do `manual inlining`
124
var log: UndoPairs = List()
127
* These two methods provide explicit locking mechanism that is overridden in SynchronizedUndoLog.
129
* The idea behind explicit locking mechanism is that all public methods that access mutable state
130
* will have to obtain the lock for their entire execution so both reads and writes can be kept in
131
* right order. Originally, that was achieved by overriding those public methods in
132
* `SynchronizedUndoLog` which was fine but expensive. The reason is that those public methods take
133
* thunk as argument and if we keep them non-final there's no way to make them inlined so thunks
136
* By using explicit locking we can achieve inlining.
138
* NOTE: They are made public for now so we can apply 'manual inlining' (copy&pasting into hot
139
* places implementation of `undo` or `undoUnless`). This should be changed back to protected
140
* once inliner is fixed.
142
def lock(): Unit = ()
143
def unlock(): Unit = ()
145
// register with the auto-clearing cache manager
146
perRunCaches.recordCache(this)
148
/** Undo all changes to constraints to type variables upto `limit`. */
149
//OPT this method is public so we can do `manual inlining`
150
def undoTo(limit: UndoPairs) {
151
assertCorrectThread()
152
while ((log ne limit) && log.nonEmpty) {
153
val (tv, constr) = log.head
159
/** No sync necessary, because record should only
160
* be called from within a undo or undoUnless block,
161
* which is already synchronized.
163
private[reflect] def record(tv: TypeVar) = {
164
log ::= ((tv, tv.constr.cloneInternal))
170
if (settings.debug.value)
171
self.log("Clearing " + log.size + " entries from the undoLog.")
177
try log.size finally unlock()
180
// `block` should not affect constraints on typevars
181
def undo[T](block: => T): T = {
187
finally undoTo(before)
191
// if `block` evaluates to false, it should not affect constraints on typevars
192
def undoUnless(block: => Boolean): Boolean = {
199
finally if (!result) undoTo(before)
206
/** A map from lists to compound types that have the given list as parents.
207
* This is used to avoid duplication in the computation of base type sequences and baseClasses.
208
* It makes use of the fact that these two operations depend only on the parents,
209
* not on the refinement.
211
val intersectionWitness = perRunCaches.newWeakMap[List[Type], WeakReference[Type]]()
213
/** A proxy for a type (identified by field `underlying`) that forwards most
214
* operations to it (for exceptions, see WrappingProxy, which forwards even more operations).
215
* every operation that is overridden for some kind of types should be forwarded.
217
trait SimpleTypeProxy extends Type {
220
// the following operations + those in RewrappingTypeProxy are all operations
221
// in class Type that are overridden in some subclass
222
// Important to keep this up-to-date when new operations are added!
223
override def isTrivial = underlying.isTrivial
224
override def isHigherKinded: Boolean = underlying.isHigherKinded
225
override def typeConstructor: Type = underlying.typeConstructor
226
override def isNotNull = underlying.isNotNull
227
override def isError = underlying.isError
228
override def isErroneous = underlying.isErroneous
229
override def isStable: Boolean = underlying.isStable
230
override def isVolatile = underlying.isVolatile
231
override def finalResultType = underlying.finalResultType
232
override def paramSectionCount = underlying.paramSectionCount
233
override def paramss = underlying.paramss
234
override def params = underlying.params
235
override def paramTypes = underlying.paramTypes
236
override def termSymbol = underlying.termSymbol
237
override def termSymbolDirect = underlying.termSymbolDirect
238
override def typeParams = underlying.typeParams
239
override def boundSyms = underlying.boundSyms
240
override def typeSymbol = underlying.typeSymbol
241
override def typeSymbolDirect = underlying.typeSymbolDirect
242
override def widen = underlying.widen
243
override def typeOfThis = underlying.typeOfThis
244
override def bounds = underlying.bounds
245
override def parents = underlying.parents
246
override def prefix = underlying.prefix
247
override def decls = underlying.decls
248
override def baseType(clazz: Symbol) = underlying.baseType(clazz)
249
override def baseTypeSeq = underlying.baseTypeSeq
250
override def baseTypeSeqDepth = underlying.baseTypeSeqDepth
251
override def baseClasses = underlying.baseClasses
254
/** A proxy for a type (identified by field `underlying`) that forwards most
255
* operations to it. Every operation that is overridden for some kind of types is
256
* forwarded here. Some operations are rewrapped again.
258
trait RewrappingTypeProxy extends SimpleTypeProxy {
259
protected def maybeRewrap(newtp: Type) = if (newtp eq underlying) this else rewrap(newtp)
260
protected def rewrap(newtp: Type): Type
262
// the following are all operations in class Type that are overridden in some subclass
263
// Important to keep this up-to-date when new operations are added!
264
override def widen = maybeRewrap(underlying.widen)
265
override def narrow = underlying.narrow
266
override def deconst = maybeRewrap(underlying.deconst)
267
override def resultType = maybeRewrap(underlying.resultType)
268
override def resultType(actuals: List[Type]) = maybeRewrap(underlying.resultType(actuals))
269
override def finalResultType = maybeRewrap(underlying.finalResultType)
270
override def paramSectionCount = 0
271
override def paramss: List[List[Symbol]] = List()
272
override def params: List[Symbol] = List()
273
override def paramTypes: List[Type] = List()
274
override def typeArgs = underlying.typeArgs
275
override def notNull = maybeRewrap(underlying.notNull)
276
override def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]) = underlying.instantiateTypeParams(formals, actuals)
277
override def skolemizeExistential(owner: Symbol, origin: AnyRef) = underlying.skolemizeExistential(owner, origin)
278
override def normalize = maybeRewrap(underlying.normalize)
279
override def dealias = maybeRewrap(underlying.dealias)
280
override def cloneInfo(owner: Symbol) = maybeRewrap(underlying.cloneInfo(owner))
281
override def atOwner(owner: Symbol) = maybeRewrap(underlying.atOwner(owner))
282
override def prefixString = underlying.prefixString
283
override def isComplete = underlying.isComplete
284
override def complete(sym: Symbol) = underlying.complete(sym)
285
override def load(sym: Symbol) { underlying.load(sym) }
286
override def withAnnotations(annots: List[AnnotationInfo]) = maybeRewrap(underlying.withAnnotations(annots))
287
override def withoutAnnotations = maybeRewrap(underlying.withoutAnnotations)
290
case object UnmappableTree extends TermTree {
291
override def toString = "<unmappable>"
293
override def tpe_=(t: Type) = if (t != NoType) {
294
throw new UnsupportedOperationException("tpe_=("+t+") inapplicable for <empty>")
298
abstract class TypeApiImpl extends TypeApi { this: Type =>
299
def declaration(name: Name): Symbol = decl(name)
300
def nonPrivateDeclaration(name: Name): Symbol = nonPrivateDecl(name)
301
def declarations = decls
302
def typeArguments = typeArgs
303
def erasure = this match {
304
case ConstantType(value) => widen.erasure
306
var result: Type = transformedType(this)
307
result = result.normalize match { // necessary to deal with erasures of HK types, typeConstructor won't work
308
case PolyType(undets, underlying) => existentialAbstraction(undets, underlying) // we don't want undets in the result
311
// erasure screws up all ThisTypes for modules into PackageTypeRefs
312
// we need to unscrew them, or certain typechecks will fail mysteriously
313
// http://groups.google.com/group/scala-internals/browse_thread/thread/6d3277ae21b6d581
314
result = result.map(tpe => tpe match {
315
case tpe: PackageTypeRef => ThisType(tpe.sym)
320
def substituteSymbols(from: List[Symbol], to: List[Symbol]): Type = substSym(from, to)
321
def substituteTypes(from: List[Symbol], to: List[Type]): Type = subst(from, to)
323
// the only thingies that we want to splice are: 1) type parameters, 2) abstract type members
324
// the thingies that we don't want to splice are: 1) concrete types (obviously), 2) existential skolems
326
this.isInstanceOf[TypeRef] && typeSymbol.isAbstractType && !typeSymbol.isExistential
330
/** Same as a call to narrow unless existentials are visible
331
* after widening the type. In that case, narrow from the widened
332
* type instead of the proxy. This gives buried existentials a
333
* chance to make peace with the other types. See SI-5330.
335
private def narrowForFindMember(tp: Type): Type = {
337
// Only narrow on widened type when we have to -- narrow is expensive unless the target is a singleton type.
338
if ((tp ne w) && containsExistential(w)) w.narrow
342
/** The base class for all types */
343
abstract class Type extends TypeApiImpl with Annotatable[Type] {
344
/** Types for which asSeenFrom always is the identity, no matter what
347
def isTrivial: Boolean = false
349
/** Is this type higher-kinded, i.e., is it a type constructor @M */
350
def isHigherKinded: Boolean = false
351
def takesTypeArgs: Boolean = this.isHigherKinded
353
/** Does this type denote a stable reference (i.e. singleton type)? */
354
def isStable: Boolean = false
356
/** Is this type dangerous (i.e. it might contain conflicting
357
* type information when empty, so that it can be constructed
358
* so that type unsoundness results.) A dangerous type has an underlying
359
* type of the form T_1 with T_n { decls }, where one of the
360
* T_i (i > 1) is an abstract type.
362
def isVolatile: Boolean = false
364
/** Is this type guaranteed not to have `null` as a value? */
365
def isNotNull: Boolean = false
367
/** Is this type a structural refinement type (it ''refines'' members that have not been inherited) */
368
def isStructuralRefinement: Boolean = false
370
/** Does this type depend immediately on an enclosing method parameter?
371
* I.e., is it a singleton type whose termSymbol refers to an argument of the symbol's owner (which is a method)?
373
def isImmediatelyDependent: Boolean = false
375
/** Is this type a dependent method type? */
376
def isDependentMethodType: Boolean = false
378
/** True for WildcardType or BoundedWildcardType. */
379
def isWildcard = false
381
/** Is this type produced as a repair for an error? */
382
def isError: Boolean = typeSymbol.isError || termSymbol.isError
384
/** Is this type produced as a repair for an error? */
385
def isErroneous: Boolean = ErroneousCollector.collect(this)
387
/** Does this type denote a reference type which can be null? */
388
// def isNullable: Boolean = false
390
/** Can this type only be subtyped by bottom types?
391
* This is assessed to be the case if the class is final,
392
* and all type parameters (if any) are invariant.
394
def isFinalType: Boolean =
395
typeSymbol.isFinal && (typeSymbol.typeParams forall symbolIsNonVariant) && prefix.isStable
397
/** Is this type completed (i.e. not a lazy type)? */
398
def isComplete: Boolean = true
400
/** If this is a lazy type, assign a new type to `sym`. */
401
def complete(sym: Symbol) {}
403
/** The term symbol associated with the type
404
* Note that the symbol of the normalized type is returned (@see normalize)
406
def termSymbol: Symbol = NoSymbol
408
/** The type symbol associated with the type
409
* Note that the symbol of the normalized type is returned (@see normalize)
410
* A type's typeSymbol should if possible not be inspected directly, due to
411
* the likelihood that what is true for tp.typeSymbol is not true for
412
* tp.sym, due to normalization.
414
def typeSymbol: Symbol = NoSymbol
416
/** The term symbol ''directly'' associated with the type.
418
def termSymbolDirect: Symbol = termSymbol
420
/** The type symbol ''directly'' associated with the type.
421
* In other words, no normalization is performed: if this is an alias type,
422
* the symbol returned is that of the alias, not the underlying type.
424
def typeSymbolDirect: Symbol = typeSymbol
426
/** The base type underlying a type proxy, identity on all other types */
427
def underlying: Type = this
429
/** Widen from singleton type to its underlying non-singleton
430
* base type by applying one or more `underlying` dereferences,
431
* identity for all other types.
433
* class Outer { class C ; val x: C }
435
* <o.x.type>.widen = o.C
437
def widen: Type = this
439
/** Map a constant type or not-null-type to its underlying base type,
440
* identity for all other types.
442
def deconst: Type = this
444
/** The type of `this` of a class type or reference type. */
445
def typeOfThis: Type = typeSymbol.typeOfThis
447
/** Map to a singleton type which is a subtype of this type.
448
* The fallback implemented here gives
449
* T.narrow = T' forSome { type T' <: T with Singleton }
450
* Overridden where we know more about where types come from.
453
Note: this implementation of narrow is theoretically superior to the one
454
in use below, but imposed a significant performance penalty. It was in trunk
455
from svn r24960 through r25080.
459
if (phase.erasedTypes) this
460
else commonOwner(this) freshExistential ".type" setInfo singletonBounds(this) tpe
463
/** Map to a singleton type which is a subtype of this type.
464
* The fallback implemented here gives:
466
* T.narrow = (T {}).this.type
468
* Overridden where we know more about where types come from.
471
if (phase.erasedTypes) this
473
val cowner = commonOwner(this)
474
refinedType(this :: Nil, cowner, EmptyScope, cowner.pos).narrow
477
/** For a TypeBounds type, itself;
478
* for a reference denoting an abstract type, its bounds,
479
* for all other types, a TypeBounds type all of whose bounds are this type.
481
def bounds: TypeBounds = TypeBounds(this, this)
483
/** For a class or intersection type, its parents.
484
* For a TypeBounds type, the parents of its hi bound.
485
* inherited by typerefs, singleton types, and refinement types,
486
* The empty list for all other types */
487
def parents: List[Type] = List()
489
/** For a class with nonEmpty parents, the first parent.
490
* Otherwise some specific fixed top type.
492
def firstParent = if (parents.nonEmpty) parents.head else ObjectClass.tpe
494
/** For a typeref or single-type, the prefix of the normalized type (@see normalize).
495
* NoType for all other types. */
496
def prefix: Type = NoType
498
/** A chain of all typeref or singletype prefixes of this type, longest first.
499
* (Only used from safeToString.)
501
def prefixChain: List[Type] = this match {
502
case TypeRef(pre, _, _) => pre :: pre.prefixChain
503
case SingleType(pre, _) => pre :: pre.prefixChain
507
/** This type, without its type arguments @M */
508
def typeConstructor: Type = this
510
/** For a typeref, its arguments. The empty list for all other types */
511
def typeArgs: List[Type] = List()
513
/** A list of placeholder types derived from the type parameters.
514
* Used by RefinedType and TypeRef.
516
protected def dummyArgs: List[Type] = typeParams map (_.typeConstructor)
518
/** For a (nullary) method or poly type, its direct result type,
519
* the type itself for all other types. */
520
def resultType: Type = this
522
def resultType(actuals: List[Type]) = this
524
/** Only used for dependent method types. */
525
def resultApprox: Type = ApproximateDependentMap(resultType)
527
/** If this is a TypeRef `clazz`[`T`], return the argument `T`
528
* otherwise return this type
530
def remove(clazz: Symbol): Type = this
532
/** For a curried/nullary method or poly type its non-method result type,
533
* the type itself for all other types */
534
def finalResultType: Type = this
536
/** For a method type, the number of its value parameter sections,
537
* 0 for all other types */
538
def paramSectionCount: Int = 0
540
/** For a method or poly type, a list of its value parameter sections,
541
* the empty list for all other types */
542
def paramss: List[List[Symbol]] = List()
544
/** For a method or poly type, its first value parameter section,
545
* the empty list for all other types */
546
def params: List[Symbol] = List()
548
/** For a method or poly type, the types of its first value parameter section,
549
* the empty list for all other types */
550
def paramTypes: List[Type] = List()
552
/** For a (potentially wrapped) poly type, its type parameters,
553
* the empty list for all other types */
554
def typeParams: List[Symbol] = List()
556
/** For a (potentially wrapped) poly or existential type, its bound symbols,
557
* the empty list for all other types */
558
def boundSyms: immutable.Set[Symbol] = emptySymbolSet
560
/** Mixin a NotNull trait unless type already has one
561
* ...if the option is given, since it is causing typing bugs.
564
if (!settings.Ynotnull.value || isNotNull || phase.erasedTypes) this
565
else NotNullType(this)
567
/** Replace formal type parameter symbols with actual type arguments.
569
* Amounts to substitution except for higher-kinded types. (See overridden method in TypeRef) -- @M
571
def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]): Type =
572
if (sameLength(formals, actuals)) this.subst(formals, actuals) else ErrorType
574
/** If this type is an existential, turn all existentially bound variables to type skolems.
575
* @param owner The owner of the created type skolems
576
* @param origin The tree whose type was an existential for which the skolem was created.
578
def skolemizeExistential(owner: Symbol, origin: AnyRef): Type = this
580
/** A simple version of skolemizeExistential for situations where
581
* owner or unpack location do not matter (typically used in subtype tests)
583
def skolemizeExistential: Type = skolemizeExistential(NoSymbol, null)
585
/** Reduce to beta eta-long normal form.
586
* Expands type aliases and converts higher-kinded TypeRefs to PolyTypes.
587
* Functions on types are also implemented as PolyTypes.
589
* Example: (in the below, `<List>` is the type constructor of List)
590
* TypeRef(pre, `<List>`, List()) is replaced by
591
* PolyType(X, TypeRef(pre, `<List>`, List(X)))
593
def normalize = this // @MAT
595
/** Expands type aliases. */
598
/** Repeatedly apply widen and dealias until they have no effect.
599
* This compensates for the fact that type aliases can hide beneath
600
* singleton types and singleton types can hide inside type aliases.
602
def dealiasWiden: Type = (
603
if (this ne widen) widen.dealiasWiden
604
else if (this ne dealias) dealias.dealiasWiden
608
/** All the types encountered in the course of dealiasing/widening,
609
* including each intermediate beta reduction step (whereas calling
610
* dealias applies as many as possible.)
612
def dealiasWidenChain: List[Type] = this :: (
613
if (this ne widen) widen.dealiasWidenChain
614
else if (this ne betaReduce) betaReduce.dealiasWidenChain
618
def etaExpand: Type = this
620
/** Performs a single step of beta-reduction on types.
627
* The following will happen after `betaReduce` is invoked:
628
* TypeRef(pre, <C>, List(Int)) is replaced by
629
* TypeRef(pre, <B>, List(Int))
631
* Unlike `dealias`, which recursively applies beta reduction, until it's stuck,
632
* `betaReduce` performs exactly one step and then returns.
634
def betaReduce: Type = this
636
/** For a classtype or refined type, its defined or declared members;
637
* inherited by subtypes and typerefs.
638
* The empty scope for all other types.
640
def decls: Scope = EmptyScope
642
/** The defined or declared members with name `name` in this type;
643
* an OverloadedSymbol if several exist, NoSymbol if none exist.
644
* Alternatives of overloaded symbol appear in the order they are declared.
646
def decl(name: Name): Symbol = findDecl(name, 0)
648
/** A list of all non-private members defined or declared in this type. */
649
def nonPrivateDecls: List[Symbol] = decls.filterNot(_.isPrivate).toList
651
/** The non-private defined or declared members with name `name` in this type;
652
* an OverloadedSymbol if several exist, NoSymbol if none exist.
653
* Alternatives of overloaded symbol appear in the order they are declared.
655
def nonPrivateDecl(name: Name): Symbol = findDecl(name, PRIVATE)
657
/** A list of all members of this type (defined or inherited)
658
* Members appear in linearization order of their owners.
659
* Members with the same owner appear in reverse order of their declarations.
661
def members: Scope = membersBasedOnFlags(0, 0)
663
/** A list of all non-private members of this type (defined or inherited) */
664
def nonPrivateMembers: Scope = membersBasedOnFlags(BridgeAndPrivateFlags, 0)
666
/** A list of all non-private members of this type (defined or inherited),
667
* admitting members with given flags `admit`
669
def nonPrivateMembersAdmitting(admit: Long): Scope = membersBasedOnFlags(BridgeAndPrivateFlags & ~admit, 0)
671
/** A list of all implicit symbols of this type (defined or inherited) */
672
def implicitMembers: Scope = membersBasedOnFlags(BridgeFlags, IMPLICIT)
674
/** A list of all deferred symbols of this type (defined or inherited) */
675
def deferredMembers: Scope = membersBasedOnFlags(BridgeFlags, DEFERRED)
677
/** The member with given name,
678
* an OverloadedSymbol if several exist, NoSymbol if none exist */
679
def member(name: Name): Symbol =
680
memberBasedOnName(name, BridgeFlags)
682
/** The non-private member with given name,
683
* an OverloadedSymbol if several exist, NoSymbol if none exist.
684
* Bridges are excluded from the result
686
def nonPrivateMember(name: Name): Symbol =
687
memberBasedOnName(name, BridgeAndPrivateFlags)
689
/** All members with the given flags, excluding bridges.
691
def membersWithFlags(requiredFlags: Long): Scope =
692
membersBasedOnFlags(BridgeFlags, requiredFlags)
694
/** All non-private members with the given flags, excluding bridges.
696
def nonPrivateMembersWithFlags(requiredFlags: Long): Scope =
697
membersBasedOnFlags(BridgeAndPrivateFlags, requiredFlags)
699
/** The non-private member with given name, admitting members with given flags `admit`.
700
* "Admitting" refers to the fact that members with a PRIVATE, BRIDGE, or VBRIDGE
701
* flag are usually excluded from findMember results, but supplying any of those flags
702
* to this method disables that exclusion.
704
* An OverloadedSymbol if several exist, NoSymbol if none exists.
706
def nonPrivateMemberAdmitting(name: Name, admit: Long): Symbol =
707
memberBasedOnName(name, BridgeAndPrivateFlags & ~admit)
709
/** The non-local member with given name,
710
* an OverloadedSymbol if several exist, NoSymbol if none exist */
711
def nonLocalMember(name: Name): Symbol =
712
memberBasedOnName(name, BridgeFlags | LOCAL)
714
/** Members excluding and requiring the given flags.
715
* Note: unfortunately it doesn't work to exclude DEFERRED this way.
717
def membersBasedOnFlags(excludedFlags: Long, requiredFlags: Long): Scope =
718
findMembers(excludedFlags, requiredFlags)
719
// findMember(nme.ANYNAME, excludedFlags, requiredFlags, false).alternatives
721
def memberBasedOnName(name: Name, excludedFlags: Long): Symbol =
722
findMember(name, excludedFlags, 0, false)
724
/** The least type instance of given class which is a supertype
725
* of this type. Example:
727
* class C extends p.D[Int]
728
* ThisType(C).baseType(D) = p.D[Int]
730
def baseType(clazz: Symbol): Type = NoType
732
/** This type as seen from prefix `pre` and class `clazz`. This means:
733
* Replace all thistypes of `clazz` or one of its subclasses
734
* by `pre` and instantiate all parameters by arguments of `pre`.
735
* Proceed analogously for thistypes referring to outer classes.
738
* class D[T] { def m: T }
739
* class C extends p.D[Int]
740
* T.asSeenFrom(ThisType(C), D) (where D is owner of m)
743
def asSeenFrom(pre: Type, clazz: Symbol): Type = {
744
val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, asSeenFromNanos) else null
748
|| phase.erasedTypes && pre.typeSymbol != ArrayClass
749
|| skipPrefixOf(pre, clazz)
753
val m = new AsSeenFromMap(pre.normalize, clazz)
755
val tp1 = existentialAbstraction(m.capturedParams, tp)
757
if (m.capturedSkolems.isEmpty) tp1
758
else deriveType(m.capturedSkolems, _.cloneSymbol setFlag CAPTURED)(tp1)
760
} finally if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
763
/** The info of `sym`, seen as a member of this type.
767
* class D[T] { def m: T }
768
* class C extends p.D[Int]
769
* ThisType(C).memberType(m) = Int
772
def memberInfo(sym: Symbol): Type = {
773
sym.info.asSeenFrom(this, sym.owner)
776
/** The type of `sym`, seen as a member of this type. */
777
def memberType(sym: Symbol): Type = sym match {
778
case meth: MethodSymbol =>
779
meth.typeAsMemberOf(this)
781
computeMemberType(sym)
784
def computeMemberType(sym: Symbol): Type = sym.tpeHK match { //@M don't prematurely instantiate higher-kinded types, they will be instantiated by transform, typedTypeApply, etc. when really necessary
785
case OverloadedType(_, alts) =>
786
OverloadedType(this, alts)
788
tp.asSeenFrom(this, sym.owner)
791
/** Substitute types `to` for occurrences of references to
792
* symbols `from` in this type.
794
def subst(from: List[Symbol], to: List[Type]): Type =
795
if (from.isEmpty) this
796
else new SubstTypeMap(from, to) apply this
798
/** Substitute symbols `to` for occurrences of symbols `from` in this type.
800
* !!! NOTE !!!: If you need to do a substThis and a substSym, the substThis has to come
801
* first, as otherwise symbols will immediately get rebound in typeRef to the old
804
def substSym(from: List[Symbol], to: List[Symbol]): Type =
805
if ((from eq to) || from.isEmpty) this
806
else new SubstSymMap(from, to) apply this
808
/** Substitute all occurrences of `ThisType(from)` in this type by `to`.
810
* !!! NOTE !!!: If you need to do a substThis and a substSym, the substThis has to come
811
* first, as otherwise symbols will immediately get rebound in typeRef to the old
814
def substThis(from: Symbol, to: Type): Type =
815
new SubstThisMap(from, to) apply this
816
def substThis(from: Symbol, to: Symbol): Type =
817
substThis(from, to.thisType)
819
/** Performs both substThis and substSym, in that order.
821
* [JZ] Reverted `SubstThisAndSymMap` from 334872, which was not the same as
822
* `substThis(from, to).substSym(symsFrom, symsTo)`.
824
* `SubstThisAndSymMap` performs a breadth-first map over this type, which meant that
825
* symbol substitution occured before `ThisType` substitution. Consequently, in substitution
826
* of a `SingleType(ThisType(`from`), sym), symbols were rebound to `from` rather than `to`.
828
def substThisAndSym(from: Symbol, to: Type, symsFrom: List[Symbol], symsTo: List[Symbol]): Type =
829
if (symsFrom eq symsTo) substThis(from, to)
830
else substThis(from, to).substSym(symsFrom, symsTo)
832
/** Returns all parts of this type which satisfy predicate `p` */
833
def filter(p: Type => Boolean): List[Type] = new FilterTypeCollector(p) collect this
834
def withFilter(p: Type => Boolean) = new FilterMapForeach(p)
836
class FilterMapForeach(p: Type => Boolean) extends FilterTypeCollector(p){
837
def foreach[U](f: Type => U): Unit = collect(Type.this) foreach f
838
def map[T](f: Type => T): List[T] = collect(Type.this) map f
841
/** Returns optionally first type (in a preorder traversal) which satisfies predicate `p`,
842
* or None if none exists.
844
def find(p: Type => Boolean): Option[Type] = new FindTypeCollector(p).collect(this)
846
/** Apply `f` to each part of this type */
847
def foreach(f: Type => Unit) { new ForEachTypeTraverser(f).traverse(this) }
849
/** Apply `pf' to each part of this type on which the function is defined */
850
def collect[T](pf: PartialFunction[Type, T]): List[T] = new CollectTypeCollector(pf).collect(this)
852
/** Apply `f` to each part of this type; children get mapped before their parents */
853
def map(f: Type => Type): Type = new TypeMap {
854
def apply(x: Type) = f(mapOver(x))
857
/** Is there part of this type which satisfies predicate `p`? */
858
def exists(p: Type => Boolean): Boolean = !find(p).isEmpty
860
/** Does this type contain a reference to this symbol? */
861
def contains(sym: Symbol): Boolean = new ContainsCollector(sym).collect(this)
863
/** Does this type contain a reference to this type */
864
def containsTp(tp: Type): Boolean = new ContainsTypeCollector(tp).collect(this)
866
/** Is this type a subtype of that type? */
867
def <:<(that: Type): Boolean = {
868
if (Statistics.canEnable) stat_<:<(that)
871
(if (explainSwitch) explain("<:", isSubType, this, that)
872
else isSubType(this, that, AnyDepth))
876
/** Is this type a subtype of that type in a pattern context?
877
* Any type arguments on the right hand side are replaced with
878
* fresh existentials, except for Arrays.
880
* See bug1434.scala for an example of code which would fail
881
* if only a <:< test were applied.
883
def matchesPattern(that: Type): Boolean = {
884
(this <:< that) || ((this, that) match {
885
case (TypeRef(_, ArrayClass, List(arg1)), TypeRef(_, ArrayClass, List(arg2))) if arg2.typeSymbol.typeParams.nonEmpty =>
886
arg1 matchesPattern arg2
887
case (_, TypeRef(_, _, args)) =>
888
val newtp = existentialAbstraction(args map (_.typeSymbol), that)
889
!(that =:= newtp) && (this <:< newtp)
895
def stat_<:<(that: Type): Boolean = {
896
if (Statistics.canEnable) Statistics.incCounter(subtypeCount)
897
val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, subtypeNanos) else null
900
(if (explainSwitch) explain("<:", isSubType, this, that)
901
else isSubType(this, that, AnyDepth))
902
if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
906
/** Is this type a weak subtype of that type? True also for numeric types, i.e. Int weak_<:< Long.
908
def weak_<:<(that: Type): Boolean = {
909
if (Statistics.canEnable) Statistics.incCounter(subtypeCount)
910
val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, subtypeNanos) else null
913
(if (explainSwitch) explain("weak_<:", isWeakSubType, this, that)
914
else isWeakSubType(this, that)))
915
if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
919
/** Is this type equivalent to that type? */
920
def =:=(that: Type): Boolean = (
922
(if (explainSwitch) explain("=", isSameType, this, that)
923
else isSameType(this, that))
926
/** Does this type implement symbol `sym` with same or stronger type? */
927
def specializes(sym: Symbol): Boolean =
928
if (explainSwitch) explain("specializes", specializesSym, this, sym)
929
else specializesSym(this, sym)
931
/** Is this type close enough to that type so that members
932
* with the two type would override each other?
934
* - Either both types are polytypes with the same number of
935
* type parameters and their result types match after renaming
936
* corresponding type parameters
937
* - Or both types are (nullary) method types with equivalent type parameter types
938
* and matching result types
939
* - Or both types are equivalent
940
* - Or phase.erasedTypes is false and both types are neither method nor
943
def matches(that: Type): Boolean = matchesType(this, that, !phase.erasedTypes)
945
/** Same as matches, except that non-method types are always assumed to match. */
946
def looselyMatches(that: Type): Boolean = matchesType(this, that, true)
948
/** The shortest sorted upwards closed array of types that contains
949
* this type as first element.
951
* A list or array of types ts is upwards closed if
954
* for all typerefs p.s[args] such that t <: p.s[args]
955
* there exists a typeref p'.s[args'] in ts such that
956
* t <: p'.s['args] <: p.s[args],
960
* for all singleton types p.s such that t <: p.s
961
* there exists a singleton type p'.s in ts such that
964
* Sorting is with respect to Symbol.isLess() on type symbols.
966
def baseTypeSeq: BaseTypeSeq = baseTypeSingletonSeq(this)
968
/** The maximum depth (@see typeDepth)
969
* of each type in the BaseTypeSeq of this type except the first.
971
def baseTypeSeqDepth: Int = 1
973
/** The list of all baseclasses of this type (including its own typeSymbol)
974
* in reverse linearization order, starting with the class itself and ending
977
def baseClasses: List[Symbol] = List()
980
* @param sym the class symbol
981
* @return the index of given class symbol in the BaseTypeSeq of this type,
982
* or -1 if no base type with given class symbol exists.
984
def baseTypeIndex(sym: Symbol): Int = {
985
val bts = baseTypeSeq
987
var hi = bts.length - 1
989
val mid = (lo + hi) / 2
990
val btssym = bts.typeSymbol(mid)
991
if (sym == btssym) return mid
992
else if (sym isLess btssym) hi = mid - 1
993
else if (btssym isLess sym) lo = mid + 1
999
/** If this is a poly- or methodtype, a copy with cloned type / value parameters
1000
* owned by `owner`. Identity for all other types.
1002
def cloneInfo(owner: Symbol) = this
1004
/** Make sure this type is correct as the info of given owner; clone it if not. */
1005
def atOwner(owner: Symbol) = this
1007
protected def objectPrefix = "object "
1008
protected def packagePrefix = "package "
1009
def trimPrefix(str: String) = str stripPrefix objectPrefix stripPrefix packagePrefix
1011
/** The string representation of this type used as a prefix */
1012
def prefixString = trimPrefix(toString) + "#"
1014
/** Convert toString avoiding infinite recursions by cutting off
1015
* after `maxTostringRecursions` recursion levels. Uses `safeToString`
1016
* to produce a string on each level.
1018
override def toString: String = typeToString(this)
1020
/** Method to be implemented in subclasses.
1021
* Converts this type to a string in calling toString for its parts.
1023
def safeToString: String = super.toString
1025
/** The string representation of this type, with singletypes explained. */
1026
def toLongString = {
1028
if (str == "type") widen.toString
1029
else if ((str endsWith ".type") && !typeSymbol.isModuleClass)
1031
case RefinedType(_, _) => "" + widen
1032
case _ => s"$str (with underlying type $widen)"
1037
/** The string representation of this type when the direct object in a sentence.
1038
* Normally this is no different from the regular representation, but modules
1039
* read better as "object Foo" here and "Foo.type" the rest of the time.
1041
def directObjectString = safeToString
1043
/** A test whether a type contains any unification type variables.
1044
* Overridden with custom logic except where trivially true.
1046
def isGround: Boolean = this match {
1047
case ThisType(_) | NoPrefix | WildcardType | NoType | ErrorType | ConstantType(_) =>
1050
typeVarToOriginMap(this) eq this
1053
/** If this is a symbol loader type, load and assign a new type to `sym`. */
1054
def load(sym: Symbol) {}
1056
private def findDecl(name: Name, excludedFlags: Int): Symbol = {
1057
var alts: List[Symbol] = List()
1058
var sym: Symbol = NoSymbol
1059
var e: ScopeEntry = decls.lookupEntry(name)
1061
if (!e.sym.hasFlag(excludedFlags)) {
1062
if (sym == NoSymbol) sym = e.sym
1064
if (alts.isEmpty) alts = sym :: Nil
1065
alts = e.sym :: alts
1068
e = decls.lookupNextEntry(e)
1070
if (alts.isEmpty) sym
1071
else (baseClasses.head.newOverloaded(this, alts))
1074
def findMembers(excludedFlags: Long, requiredFlags: Long): Scope = {
1075
// if this type contains type variables, put them to sleep for a while -- don't just wipe them out by
1076
// replacing them by the corresponding type parameter, as that messes up (e.g.) type variables in type refinements
1077
// without this, the matchesType call would lead to type variables on both sides
1078
// of a subtyping/equality judgement, which can lead to recursive types being constructed.
1079
// See (t0851) for a situation where this happens.
1080
val suspension: List[TypeVar] = if (this.isGround) null else suspendTypeVarsInType(this)
1082
if (Statistics.canEnable) Statistics.incCounter(findMembersCount)
1083
val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, findMembersNanos) else null
1085
//Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG
1086
var members: Scope = null
1087
var required = requiredFlags
1088
var excluded = excludedFlags | DEFERRED
1090
var self: Type = null
1093
val bcs0 = baseClasses
1095
while (!bcs.isEmpty) {
1096
val decls = bcs.head.info.decls
1097
var entry = decls.elems
1098
while (entry ne null) {
1100
val flags = sym.flags
1101
if ((flags & required) == required) {
1102
val excl = flags & excluded
1104
(// omit PRIVATE LOCALS unless selector class is contained in class owning the def.
1106
(flags & PrivateLocal) != PrivateLocal ||
1107
(bcs0.head.hasTransOwner(bcs.head)))) {
1108
if (members eq null) members = newFindMemberScope
1109
var others: ScopeEntry = members.lookupEntry(sym.name)
1110
var symtpe: Type = null
1111
while ((others ne null) && {
1112
val other = others.sym
1114
((other.owner eq sym.owner) ||
1115
(flags & PRIVATE) != 0 || {
1116
if (self eq null) self = narrowForFindMember(this)
1117
if (symtpe eq null) symtpe = self.memberType(sym)
1118
!(self.memberType(other) matches symtpe)
1120
others = members lookupNextEntry others
1122
if (others eq null) members enter sym
1123
} else if (excl == DEFERRED) {
1128
} // while (entry ne null)
1129
// excluded = excluded | LOCAL
1131
} // while (!bcs.isEmpty)
1132
required |= DEFERRED
1133
excluded &= ~(DEFERRED.toLong)
1134
} // while (continue)
1135
if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
1136
if (suspension ne null) suspension foreach (_.suspended = false)
1137
if (members eq null) EmptyScope else members
1141
* Find member(s) in this type. If several members matching criteria are found, they are
1142
* returned in an OverloadedSymbol
1144
* @param name The member's name, where nme.ANYNAME means `unspecified`
1145
* @param excludedFlags Returned members do not have these flags
1146
* @param requiredFlags Returned members do have these flags
1147
* @param stableOnly If set, return only members that are types or stable values
1149
//TODO: use narrow only for modules? (correct? efficiency gain?)
1150
def findMember(name: Name, excludedFlags: Long, requiredFlags: Long, stableOnly: Boolean): Symbol = {
1151
// if this type contains type variables, put them to sleep for a while -- don't just wipe them out by
1152
// replacing them by the corresponding type parameter, as that messes up (e.g.) type variables in type refinements
1153
// without this, the matchesType call would lead to type variables on both sides
1154
// of a subtyping/equality judgement, which can lead to recursive types being constructed.
1155
// See (t0851) for a situation where this happens.
1156
val suspension: List[TypeVar] = if (this.isGround) null else suspendTypeVarsInType(this)
1158
if (Statistics.canEnable) Statistics.incCounter(findMemberCount)
1159
val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, findMemberNanos) else null
1161
//Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG
1162
var member: Symbol = NoSymbol
1163
var members: List[Symbol] = null
1164
var lastM: ::[Symbol] = null
1165
var membertpe: Type = null
1166
var required = requiredFlags
1167
var excluded = excludedFlags | DEFERRED
1169
var self: Type = null
1173
val bcs0 = baseClasses
1175
// omit PRIVATE LOCALS unless selector class is contained in class owning the def.
1176
def admitPrivateLocal(owner: Symbol): Boolean = {
1177
val selectorClass = this match {
1178
case tt: ThisType => tt.sym // SI-7507 the first base class is not necessarily the selector class.
1181
selectorClass.hasTransOwner(owner)
1183
while (!bcs.isEmpty) {
1184
val decls = bcs.head.info.decls
1185
var entry = decls.lookupEntry(name)
1186
while (entry ne null) {
1188
val flags = sym.flags
1189
if ((flags & required) == required) {
1190
val excl = flags & excluded
1194
(flags & PrivateLocal) != PrivateLocal ||
1195
admitPrivateLocal(bcs.head))) {
1196
if (name.isTypeName || stableOnly && sym.isStable) {
1197
if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
1198
if (suspension ne null) suspension foreach (_.suspended = false)
1200
} else if (member eq NoSymbol) {
1202
} else if (members eq null) {
1203
if ((member ne sym) &&
1204
((member.owner eq sym.owner) ||
1205
(flags & PRIVATE) != 0 || {
1206
if (self eq null) self = narrowForFindMember(this)
1207
if (membertpe eq null) membertpe = self.memberType(member)
1208
!(membertpe matches self.memberType(sym))
1210
lastM = new ::(sym, null)
1211
members = member :: lastM
1214
var others: List[Symbol] = members
1215
var symtpe: Type = null
1216
while ((others ne null) && {
1217
val other = others.head
1219
((other.owner eq sym.owner) ||
1220
(flags & PRIVATE) != 0 || {
1221
if (self eq null) self = narrowForFindMember(this)
1222
if (symtpe eq null) symtpe = self.memberType(sym)
1223
!(self.memberType(other) matches symtpe)
1225
others = others.tail
1227
if (others eq null) {
1228
val lastM1 = new ::(sym, null)
1233
} else if (excl == DEFERRED) {
1237
entry = decls lookupNextEntry entry
1238
} // while (entry ne null)
1239
// excluded = excluded | LOCAL
1240
bcs = if (name == nme.CONSTRUCTOR) Nil else bcs.tail
1241
} // while (!bcs.isEmpty)
1242
required |= DEFERRED
1243
excluded &= ~(DEFERRED.toLong)
1244
} // while (continue)
1245
if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
1246
if (suspension ne null) suspension foreach (_.suspended = false)
1247
if (members eq null) {
1248
if (member == NoSymbol) if (Statistics.canEnable) Statistics.incCounter(noMemberCount)
1251
if (Statistics.canEnable) Statistics.incCounter(multMemberCount)
1253
baseClasses.head.newOverloaded(this, members)
1257
/** The (existential or otherwise) skolems and existentially quantified variables which are free in this type */
1258
def skolemsExceptMethodTypeParams: List[Symbol] = {
1259
var boundSyms: List[Symbol] = List()
1260
var skolems: List[Symbol] = List()
1263
case ExistentialType(quantified, qtpe) =>
1264
boundSyms = boundSyms ::: quantified
1265
case TypeRef(_, sym, _) =>
1266
if ((sym.isExistentialSkolem || sym.isGADTSkolem) && // treat GADT skolems like existential skolems
1267
!((boundSyms contains sym) || (skolems contains sym)))
1268
skolems = sym :: skolems
1275
// Implementation of Annotatable for all types but AnnotatedType, which
1277
def annotations: List[AnnotationInfo] = Nil
1278
def withoutAnnotations: Type = this
1279
def filterAnnotations(p: AnnotationInfo => Boolean): Type = this
1280
def setAnnotations(annots: List[AnnotationInfo]): Type = annotatedType(annots, this)
1281
def withAnnotations(annots: List[AnnotationInfo]): Type = annotatedType(annots, this)
1283
/** Remove any annotations from this type and from any
1284
* types embedded in this type. */
1285
def stripAnnotations = StripAnnotationsMap(this)
1287
/** Set the self symbol of an annotated type, or do nothing
1289
def withSelfsym(sym: Symbol) = this
1291
/** The selfsym of an annotated type, or NoSymbol of anything else */
1292
def selfsym: Symbol = NoSymbol
1294
/** The kind of this type; used for debugging */
1295
def kind: String = "unknown type of class "+getClass()
1298
// Subclasses ------------------------------------------------------------
1301
* A type that can be passed to unique(..) and be stored in the uniques map.
1303
abstract class UniqueType extends Type with Product {
1304
final override val hashCode = computeHashCode
1305
protected def computeHashCode = scala.runtime.ScalaRunTime._hashCode(this)
1308
/** A base class for types that defer some operations
1309
* to their immediate supertype.
1311
abstract class SubType extends UniqueType {
1313
override def parents: List[Type] = supertype.parents
1314
override def decls: Scope = supertype.decls
1315
override def baseType(clazz: Symbol): Type = supertype.baseType(clazz)
1316
override def baseTypeSeq: BaseTypeSeq = supertype.baseTypeSeq
1317
override def baseTypeSeqDepth: Int = supertype.baseTypeSeqDepth
1318
override def baseClasses: List[Symbol] = supertype.baseClasses
1319
override def isNotNull = supertype.isNotNull
1322
case class NotNullType(override val underlying: Type) extends SubType with RewrappingTypeProxy {
1323
def supertype = underlying
1324
protected def rewrap(newtp: Type): Type = NotNullType(newtp)
1325
override def isNotNull: Boolean = true
1326
override def notNull = this
1327
override def deconst: Type = underlying //todo: needed?
1328
override def safeToString: String = underlying.toString + " with NotNull"
1329
override def kind = "NotNullType"
1332
/** A base class for types that represent a single value
1333
* (single-types and this-types).
1335
abstract class SingletonType extends SubType with SimpleTypeProxy {
1336
def supertype = underlying
1337
override def isTrivial = false
1338
override def isStable = true
1339
override def isVolatile = underlying.isVolatile
1340
override def widen: Type = underlying.widen
1341
override def baseTypeSeq: BaseTypeSeq = {
1342
if (Statistics.canEnable) Statistics.incCounter(singletonBaseTypeSeqCount)
1343
underlying.baseTypeSeq prepend this
1345
override def isHigherKinded = false // singleton type classifies objects, thus must be kind *
1346
override def safeToString: String = {
1347
// Avoiding printing Predef.type and scala.package.type as "type",
1348
// since in all other cases we omit those prefixes.
1349
val pre = underlying.typeSymbol.skipPackageObject
1350
if (pre.isOmittablePrefix) pre.fullName + ".type"
1351
else prefixString + "type"
1355
override def typeOfThis: Type = typeSymbol.typeOfThis
1356
override def bounds: TypeBounds = TypeBounds(this, this)
1357
override def prefix: Type = NoType
1358
override def typeArgs: List[Type] = List()
1359
override def typeParams: List[Symbol] = List()
1363
/** An object representing an erroneous type */
1364
case object ErrorType extends Type {
1365
// todo see whether we can do without
1366
override def isError: Boolean = true
1367
override def decls: Scope = new ErrorScope(NoSymbol)
1368
override def findMember(name: Name, excludedFlags: Long, requiredFlags: Long, stableOnly: Boolean): Symbol = {
1369
var sym = decls lookup name
1370
if (sym == NoSymbol) {
1371
sym = NoSymbol.newErrorSymbol(name)
1376
override def baseType(clazz: Symbol): Type = this
1377
override def safeToString: String = "<error>"
1378
override def narrow: Type = this
1379
// override def isNullable: Boolean = true
1380
override def kind = "ErrorType"
1383
/** An object representing an unknown type, used during type inference.
1384
* If you see WildcardType outside of inference it is almost certainly a bug.
1386
case object WildcardType extends Type {
1387
override def isWildcard = true
1388
override def safeToString: String = "?"
1389
// override def isNullable: Boolean = true
1390
override def kind = "WildcardType"
1392
/** BoundedWildcardTypes, used only during type inference, are created in
1393
* two places that I can find:
1395
* 1. If the expected type of an expression is an existential type,
1396
* its hidden symbols are replaced with bounded wildcards.
1397
* 2. When an implicit conversion is being sought based in part on
1398
* the name of a method in the converted type, a HasMethodMatching
1399
* type is created: a MethodType with parameters typed as
1400
* BoundedWildcardTypes.
1402
case class BoundedWildcardType(override val bounds: TypeBounds) extends Type with BoundedWildcardTypeApi {
1403
override def isWildcard = true
1404
override def safeToString: String = "?" + bounds
1405
override def kind = "BoundedWildcardType"
1408
object BoundedWildcardType extends BoundedWildcardTypeExtractor
1410
/** An object representing a non-existing type */
1411
case object NoType extends Type {
1412
override def isTrivial: Boolean = true
1413
override def safeToString: String = "<notype>"
1414
// override def isNullable: Boolean = true
1415
override def kind = "NoType"
1418
/** An object representing a non-existing prefix */
1419
case object NoPrefix extends Type {
1420
override def isTrivial: Boolean = true
1421
override def isStable: Boolean = true
1422
override def prefixString = ""
1423
override def safeToString: String = "<noprefix>"
1424
// override def isNullable: Boolean = true
1425
override def kind = "NoPrefixType"
1428
/** A class for this-types of the form <sym>.this.type
1430
abstract case class ThisType(sym: Symbol) extends SingletonType with ThisTypeApi {
1432
// SI-6640 allow StubSymbols to reveal what's missing from the classpath before we trip the assertion.
1434
abort(s"ThisType($sym) for sym which is not a class")
1437
//assert(sym.isClass && !sym.isModuleClass || sym.isRoot, sym)
1438
override def isTrivial: Boolean = sym.isPackageClass
1439
override def isNotNull = true
1440
override def typeSymbol = sym
1441
override def underlying: Type = sym.typeOfThis
1442
override def isVolatile = false
1443
override def isHigherKinded = sym.isRefinementClass && underlying.isHigherKinded
1444
override def prefixString =
1445
if (settings.debug.value) sym.nameString + ".this."
1446
else if (sym.isAnonOrRefinementClass) "this."
1447
else if (sym.isOmittablePrefix) ""
1448
else if (sym.isModuleClass) sym.fullNameString + "."
1449
else sym.nameString + ".this."
1450
override def safeToString: String =
1451
if (sym.isEffectiveRoot) "" + sym.name
1452
else super.safeToString
1453
override def narrow: Type = this
1454
override def kind = "ThisType"
1457
final class UniqueThisType(sym: Symbol) extends ThisType(sym) { }
1459
object ThisType extends ThisTypeExtractor {
1460
def apply(sym: Symbol): Type = (
1461
if (!phase.erasedTypes) unique(new UniqueThisType(sym))
1462
else if (sym.isImplClass) sym.typeOfThis
1467
/** A class for singleton types of the form `<prefix>.<sym.name>.type`.
1468
* Cannot be created directly; one should always use `singleType` for creation.
1470
abstract case class SingleType(pre: Type, sym: Symbol) extends SingletonType with SingleTypeApi {
1471
private var trivial: ThreeValue = UNKNOWN
1472
override def isTrivial: Boolean = {
1473
if (trivial == UNKNOWN) trivial = fromBoolean(pre.isTrivial)
1476
override def isGround = sym.isPackageClass || pre.isGround
1478
// override def isNullable = underlying.isNullable
1479
override def isNotNull = underlying.isNotNull
1480
private[reflect] var underlyingCache: Type = NoType
1481
private[reflect] var underlyingPeriod = NoPeriod
1482
override def underlying: Type = {
1483
val cache = underlyingCache
1484
if (underlyingPeriod == currentPeriod && cache != null) cache
1486
defineUnderlyingOfSingleType(this)
1491
// more precise conceptually, but causes cyclic errors: (paramss exists (_ contains sym))
1492
override def isImmediatelyDependent = (sym ne NoSymbol) && (sym.owner.isMethod && sym.isValueParameter)
1494
override def isVolatile : Boolean = underlying.isVolatile && !sym.isStable
1496
override def narrow: Type = {
1497
if (phase.erasedTypes) this
1499
val thissym = refinedType(List(this), sym.owner, EmptyScope).typeSymbol
1500
if (sym.owner != NoSymbol) {
1501
//Console.println("narrowing module " + sym + thissym.owner);
1502
thissym.typeOfThis = this
1508
override def narrow: Type = this
1510
override def termSymbol = sym
1511
override def prefix: Type = pre
1512
override def prefixString = (
1513
if (sym.skipPackageObject.isOmittablePrefix) ""
1514
else if (sym.isPackageObjectOrClass) pre.prefixString
1515
else pre.prefixString + sym.nameString + "."
1517
override def kind = "SingleType"
1520
final class UniqueSingleType(pre: Type, sym: Symbol) extends SingleType(pre, sym)
1522
object SingleType extends SingleTypeExtractor {
1523
def apply(pre: Type, sym: Symbol): Type = {
1524
unique(new UniqueSingleType(pre, sym))
1528
protected def defineUnderlyingOfSingleType(tpe: SingleType) = {
1529
val period = tpe.underlyingPeriod
1530
if (period != currentPeriod) {
1531
tpe.underlyingPeriod = currentPeriod
1532
if (!isValid(period)) {
1533
// [Eugene to Paul] needs review
1534
tpe.underlyingCache = if (tpe.sym == NoSymbol) ThisType(rootMirror.RootClass) else tpe.pre.memberType(tpe.sym).resultType;
1535
assert(tpe.underlyingCache ne tpe, tpe)
1540
abstract case class SuperType(thistpe: Type, supertpe: Type) extends SingletonType with SuperTypeApi {
1541
private var trivial: ThreeValue = UNKNOWN
1542
override def isTrivial: Boolean = {
1543
if (trivial == UNKNOWN) trivial = fromBoolean(thistpe.isTrivial && supertpe.isTrivial)
1546
override def isNotNull = true;
1547
override def typeSymbol = thistpe.typeSymbol
1548
override def underlying = supertpe
1549
override def prefix: Type = supertpe.prefix
1550
override def prefixString = thistpe.prefixString.replaceAll("""\bthis\.$""", "super.")
1551
override def narrow: Type = thistpe.narrow
1552
override def kind = "SuperType"
1555
final class UniqueSuperType(thistp: Type, supertp: Type) extends SuperType(thistp, supertp)
1557
object SuperType extends SuperTypeExtractor {
1558
def apply(thistp: Type, supertp: Type): Type = {
1559
if (phase.erasedTypes) supertp
1560
else unique(new UniqueSuperType(thistp, supertp))
1564
/** A class for the bounds of abstract types and type parameters
1566
abstract case class TypeBounds(lo: Type, hi: Type) extends SubType with TypeBoundsApi {
1568
override def isTrivial: Boolean = lo.isTrivial && hi.isTrivial
1569
override def bounds: TypeBounds = this
1570
def containsType(that: Type) = that match {
1571
case TypeBounds(_, _) => that <:< this
1572
case _ => lo <:< that && that <:< hi
1574
private def lowerString = if (emptyLowerBound) "" else " >: " + lo
1575
private def upperString = if (emptyUpperBound) "" else " <: " + hi
1576
private def emptyLowerBound = typeIsNothing(lo)
1577
private def emptyUpperBound = typeIsAny(hi)
1578
def isEmptyBounds = emptyLowerBound && emptyUpperBound
1580
// override def isNullable: Boolean = NullClass.tpe <:< lo;
1581
override def safeToString = lowerString + upperString
1582
override def kind = "TypeBoundsType"
1585
final class UniqueTypeBounds(lo: Type, hi: Type) extends TypeBounds(lo, hi)
1587
object TypeBounds extends TypeBoundsExtractor {
1588
def empty: TypeBounds = apply(NothingClass.tpe, AnyClass.tpe)
1589
def upper(hi: Type): TypeBounds = apply(NothingClass.tpe, hi)
1590
def lower(lo: Type): TypeBounds = apply(lo, AnyClass.tpe)
1591
def apply(lo: Type, hi: Type): TypeBounds = {
1592
unique(new UniqueTypeBounds(lo, hi)).asInstanceOf[TypeBounds]
1596
/** A common base class for intersection types and class types
1598
abstract class CompoundType extends Type {
1600
private[reflect] var baseTypeSeqCache: BaseTypeSeq = _
1601
private[reflect] var baseTypeSeqPeriod = NoPeriod
1602
private[reflect] var baseClassesCache: List[Symbol] = _
1603
private[reflect] var baseClassesPeriod = NoPeriod
1605
override def baseTypeSeq: BaseTypeSeq = {
1606
val cached = baseTypeSeqCache
1607
if (baseTypeSeqPeriod == currentPeriod && cached != null && cached != undetBaseTypeSeq)
1610
defineBaseTypeSeqOfCompoundType(this)
1611
if (baseTypeSeqCache eq undetBaseTypeSeq)
1612
throw new RecoverableCyclicReference(typeSymbol)
1618
override def baseTypeSeqDepth: Int = baseTypeSeq.maxDepth
1620
override def baseClasses: List[Symbol] = {
1621
val cached = baseClassesCache
1622
if (baseClassesPeriod == currentPeriod && cached != null) cached
1624
defineBaseClassesOfCompoundType(this)
1625
if (baseClassesCache eq null)
1626
throw new RecoverableCyclicReference(typeSymbol)
1632
/** The slightly less idiomatic use of Options is due to
1633
* performance considerations. A version using for comprehensions
1634
* might be too slow (this is deemed a hotspot of the type checker).
1636
* See with Martin before changing this method.
1638
def memo[A](op1: => A)(op2: Type => A): A = {
1639
def updateCache(): A = {
1640
intersectionWitness(parents) = new WeakReference(this)
1644
intersectionWitness get parents match {
1647
case Some(w) => if (w eq this) op1 else op2(w)
1648
case None => updateCache()
1650
case None => updateCache()
1654
override def baseType(sym: Symbol): Type = {
1655
val index = baseTypeIndex(sym)
1656
if (index >= 0) baseTypeSeq(index) else NoType
1659
override def narrow: Type = typeSymbol.thisType
1660
override def isNotNull: Boolean = parents exists typeIsNotNull
1662
override def isStructuralRefinement: Boolean =
1663
typeSymbol.isAnonOrRefinementClass && (decls exists symbolIsPossibleInRefinement)
1665
// override def isNullable: Boolean =
1666
// parents forall (p => p.isNullable && !p.typeSymbol.isAbstractType);
1668
override def safeToString: String = parentsString(parents) + (
1669
(if (settings.debug.value || parents.isEmpty || (decls.elems ne null))
1670
fullyInitializeScope(decls).mkString("{", "; ", "}") else "")
1674
protected def defineBaseTypeSeqOfCompoundType(tpe: CompoundType) = {
1675
val period = tpe.baseTypeSeqPeriod
1676
if (period != currentPeriod) {
1677
tpe.baseTypeSeqPeriod = currentPeriod
1678
if (!isValidForBaseClasses(period)) {
1679
if (tpe.parents exists typeContainsTypeVar) {
1680
// rename type vars to fresh type params, take base type sequence of
1681
// resulting type, and rename back all the entries in that sequence
1682
var tvs = Set[TypeVar]()
1683
for (p <- tpe.parents)
1684
for (t <- p) t match {
1685
case tv: TypeVar => tvs += tv
1688
val varToParamMap: Map[Type, Symbol] =
1689
mapFrom[TypeVar, Type, Symbol](tvs.toList)(_.origin.typeSymbol.cloneSymbol)
1690
val paramToVarMap = varToParamMap map (_.swap)
1691
val varToParam = new TypeMap {
1692
def apply(tp: Type) = varToParamMap get tp match {
1693
case Some(sym) => sym.tpe
1694
case _ => mapOver(tp)
1697
val paramToVar = new TypeMap {
1698
def apply(tp: Type) = tp match {
1699
case TypeRef(_, tsym, _) if paramToVarMap.isDefinedAt(tsym) => paramToVarMap(tsym)
1700
case _ => mapOver(tp)
1703
val bts = copyRefinedType(tpe.asInstanceOf[RefinedType], tpe.parents map varToParam, varToParam mapOver tpe.decls).baseTypeSeq
1704
tpe.baseTypeSeqCache = bts lateMap paramToVar
1706
if (Statistics.canEnable) Statistics.incCounter(compoundBaseTypeSeqCount)
1707
val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, baseTypeSeqNanos) else null
1709
tpe.baseTypeSeqCache = undetBaseTypeSeq
1710
tpe.baseTypeSeqCache =
1711
if (tpe.typeSymbol.isRefinementClass)
1712
tpe.memo(compoundBaseTypeSeq(tpe))(_.baseTypeSeq updateHead tpe.typeSymbol.tpe)
1714
compoundBaseTypeSeq(tpe)
1716
if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
1718
// [Martin] suppressing memo-ization solves the problem with "same type after erasure" errors
1719
// when compiling with
1720
// scalac scala.collection.IterableViewLike.scala scala.collection.IterableLike.scala
1721
// I have not yet figured out precisely why this is the case.
1722
// My current assumption is that taking memos forces baseTypeSeqs to be computed
1723
// at stale types (i.e. the underlying typeSymbol has already another type).
1724
// I do not yet see precisely why this would cause a problem, but it looks
1725
// fishy in any case.
1729
//Console.println("baseTypeSeq(" + typeSymbol + ") = " + baseTypeSeqCache.toList);//DEBUG
1730
if (tpe.baseTypeSeqCache eq undetBaseTypeSeq)
1731
throw new TypeError("illegal cyclic inheritance involving " + tpe.typeSymbol)
1734
protected def defineBaseClassesOfCompoundType(tpe: CompoundType) = {
1735
def computeBaseClasses: List[Symbol] =
1736
if (tpe.parents.isEmpty) List(tpe.typeSymbol)
1738
//Console.println("computing base classes of " + typeSymbol + " at phase " + phase);//DEBUG
1739
// optimized, since this seems to be performance critical
1740
val superclazz = tpe.firstParent
1741
var mixins = tpe.parents.tail
1742
val sbcs = superclazz.baseClasses
1744
def isNew(clazz: Symbol): Boolean =
1745
superclazz.baseTypeIndex(clazz) < 0 &&
1747
while ((p ne sbcs) && (p.head != clazz)) p = p.tail;
1750
while (!mixins.isEmpty) {
1751
def addMixinBaseClasses(mbcs: List[Symbol]): List[Symbol] =
1752
if (mbcs.isEmpty) bcs
1753
else if (isNew(mbcs.head)) mbcs.head :: addMixinBaseClasses(mbcs.tail)
1754
else addMixinBaseClasses(mbcs.tail)
1755
bcs = addMixinBaseClasses(mixins.head.baseClasses)
1756
mixins = mixins.tail
1758
tpe.typeSymbol :: bcs
1760
val period = tpe.baseClassesPeriod
1761
if (period != currentPeriod) {
1762
tpe.baseClassesPeriod = currentPeriod
1763
if (!isValidForBaseClasses(period)) {
1764
val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, baseClassesNanos) else null
1766
tpe.baseClassesCache = null
1767
tpe.baseClassesCache = tpe.memo(computeBaseClasses)(tpe.typeSymbol :: _.baseClasses.tail)
1769
if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
1773
if (tpe.baseClassesCache eq null)
1774
throw new TypeError("illegal cyclic reference involving " + tpe.typeSymbol)
1777
/** A class representing intersection types with refinements of the form
1778
* `<parents_0> with ... with <parents_n> { decls }`
1779
* Cannot be created directly;
1780
* one should always use `refinedType` for creation.
1782
case class RefinedType(override val parents: List[Type],
1783
override val decls: Scope) extends CompoundType with RefinedTypeApi {
1785
override def isHigherKinded = (
1787
(parents forall typeIsHigherKinded) &&
1791
override def typeParams =
1792
if (isHigherKinded) firstParent.typeParams
1793
else super.typeParams
1795
//@M may result in an invalid type (references to higher-order args become dangling )
1796
override def typeConstructor =
1797
copyRefinedType(this, parents map (_.typeConstructor), decls)
1799
final override def normalize: Type =
1800
if (phase.erasedTypes) normalizeImpl
1802
if (normalized eq null) normalized = normalizeImpl
1806
private var normalized: Type = _
1807
private def normalizeImpl = {
1808
// TODO see comments around def intersectionType and def merge
1809
def flatten(tps: List[Type]): List[Type] = tps flatMap { case RefinedType(parents, ds) if ds.isEmpty => flatten(parents) case tp => List(tp) }
1810
val flattened = flatten(parents).distinct
1811
if (decls.isEmpty && hasLength(flattened, 1)) {
1813
} else if (flattened != parents) {
1814
refinedType(flattened, if (typeSymbol eq NoSymbol) NoSymbol else typeSymbol.owner, decls, NoPosition)
1815
} else if (isHigherKinded) {
1816
// MO to AM: This is probably not correct
1817
// If they are several higher-kinded parents with different bounds we need
1818
// to take the intersection of their bounds
1823
case TypeRef(pre, sym, List()) => TypeRef(pre, sym, dummyArgs)
1828
} else super.normalize
1831
/** A refined type P1 with ... with Pn { decls } is volatile if
1832
* one of the parent types Pi is an abstract type, and
1833
* either i > 1, or decls or a following parent Pj, j > 1, contributes
1834
* an abstract member.
1835
* A type contributes an abstract member if it has an abstract member which
1836
* is also a member of the whole refined type. A scope `decls` contributes
1837
* an abstract member if it has an abstract definition which is also
1838
* a member of the whole type.
1840
override def isVolatile = {
1841
def isVisible(m: Symbol) =
1842
this.nonPrivateMember(m.name).alternatives contains m
1843
def contributesAbstractMembers(p: Type) =
1844
p.deferredMembers exists isVisible
1846
((parents exists (_.isVolatile))
1848
(parents dropWhile (! _.typeSymbol.isAbstractType) match {
1849
case ps @ (_ :: ps1) =>
1851
(ps1 exists contributesAbstractMembers) ||
1852
(decls.iterator exists (m => m.isDeferred && isVisible(m)))
1857
override def kind = "RefinedType"
1860
final class RefinedType0(parents: List[Type], decls: Scope, clazz: Symbol) extends RefinedType(parents, decls) {
1861
override def typeSymbol = clazz
1864
object RefinedType extends RefinedTypeExtractor {
1865
def apply(parents: List[Type], decls: Scope, clazz: Symbol): RefinedType =
1866
new RefinedType0(parents, decls, clazz)
1869
/** Overridden in reflection compiler */
1870
def validateClassInfo(tp: ClassInfoType) {}
1872
/** A class representing a class info
1874
case class ClassInfoType(
1875
override val parents: List[Type],
1876
override val decls: Scope,
1877
override val typeSymbol: Symbol) extends CompoundType with ClassInfoTypeApi
1879
validateClassInfo(this)
1882
private final val NonExpansive = 0
1883
private final val Expansive = 1
1885
/** initialization states */
1886
private final val UnInitialized = 0
1887
private final val Initializing = 1
1888
private final val Initialized = 2
1890
private type RefMap = Map[Symbol, immutable.Set[Symbol]]
1892
/** All type parameters reachable from given type parameter
1893
* by a path which contains at least one expansive reference.
1894
* @See Kennedy, Pierce: On Decidability of Nominal Subtyping with Variance
1896
private[scala] def expansiveRefs(tparam: Symbol) = {
1897
if (state == UnInitialized) {
1899
while (state != Initialized) propagate()
1901
getRefs(Expansive, tparam)
1904
/* The rest of this class is auxiliary code for `expansiveRefs`
1907
/** The type parameters which are referenced type parameters of this class.
1908
* Two entries: refs(0): Non-expansive references
1909
* refs(1): Expansive references
1910
* Syncnote: This var need not be protected with synchronized, because
1911
* it is accessed only from expansiveRefs, which is called only from
1914
private var refs: Array[RefMap] = _
1916
/** The initialization state of the class: UnInialized --> Initializing --> Initialized
1917
* Syncnote: This var need not be protected with synchronized, because
1918
* it is accessed only from expansiveRefs, which is called only from
1921
private var state = UnInitialized
1923
/** Get references for given type parameter
1924
* @param which in {NonExpansive, Expansive}
1925
* @param from The type parameter from which references originate.
1927
private def getRefs(which: Int, from: Symbol): Set[Symbol] = refs(which) get from match {
1928
case Some(set) => set
1932
/** Augment existing refs map with reference <pre>from -> to</pre>
1933
* @param which <- {NonExpansive, Expansive}
1935
private def addRef(which: Int, from: Symbol, to: Symbol) {
1936
refs(which) = refs(which) + (from -> (getRefs(which, from) + to))
1939
/** Augment existing refs map with references <pre>from -> sym</pre>, for
1940
* all elements <pre>sym</pre> of set `to`.
1941
* @param which <- {NonExpansive, Expansive}
1943
private def addRefs(which: Int, from: Symbol, to: Set[Symbol]) {
1944
refs(which) = refs(which) + (from -> (getRefs(which, from) ++ to))
1947
/** The ClassInfoType which belongs to the class containing given type parameter
1949
private def classInfo(tparam: Symbol): ClassInfoType =
1950
tparam.owner.info.resultType match {
1951
case ci: ClassInfoType => ci
1952
case _ => classInfo(ObjectClass) // something's wrong; fall back to safe value
1953
// (this can happen only for erroneous programs).
1956
private object enterRefs extends TypeMap {
1957
private var tparam: Symbol = _
1959
def apply(tp: Type): Type = {
1961
case tr @ TypeRef(_, sym, args) if args.nonEmpty =>
1962
val tparams = tr.initializedTypeParams
1963
if (settings.debug.value && !sameLength(tparams, args))
1964
debugwarn("Mismatched zip in computeRefs(): " + sym.info.typeParams + ", " + args)
1966
foreach2(tparams, args) { (tparam1, arg) =>
1967
if (arg contains tparam) {
1968
addRef(NonExpansive, tparam, tparam1)
1969
if (arg.typeSymbol != tparam)
1970
addRef(Expansive, tparam, tparam1)
1977
def enter(tparam0: Symbol, parent: Type) {
1978
this.tparam = tparam0
1983
/** Compute initial (one-step) references and set state to `Initializing`.
1985
private def computeRefs() {
1986
refs = Array(Map(), Map())
1987
typeSymbol.typeParams foreach { tparam =>
1988
parents foreach { p =>
1989
enterRefs.enter(tparam, p)
1992
state = Initializing
1995
/** Propagate to form transitive closure.
1996
* Set state to Initialized if no change resulted from propagation.
1997
* @return true iff there as a change in last iteration
1999
private def propagate(): Boolean = {
2000
if (state == UnInitialized) computeRefs()
2001
//Console.println("Propagate "+symbol+", initial expansive = "+refs(Expansive)+", nonexpansive = "+refs(NonExpansive))//DEBUG
2002
val lastRefs = Array(refs(0), refs(1))
2005
for ((from, targets) <- refs(NonExpansive).iterator)
2006
for (target <- targets) {
2007
var thatInfo = classInfo(target)
2008
if (thatInfo.state != Initialized)
2009
change = change | thatInfo.propagate()
2010
addRefs(NonExpansive, from, thatInfo.getRefs(NonExpansive, target))
2011
addRefs(Expansive, from, thatInfo.getRefs(Expansive, target))
2013
for ((from, targets) <- refs(Expansive).iterator)
2014
for (target <- targets) {
2015
var thatInfo = classInfo(target)
2016
if (thatInfo.state != Initialized)
2017
change = change | thatInfo.propagate()
2018
addRefs(Expansive, from, thatInfo.getRefs(NonExpansive, target))
2020
change = change || refs(0) != lastRefs(0) || refs(1) != lastRefs(1)
2021
if (change) state = Initializing
2022
//else Console.println("Propagate "+symbol+", final expansive = "+refs(Expansive)+", nonexpansive = "+refs(NonExpansive))//DEBUG
2026
// override def isNullable: Boolean =
2027
// symbol == AnyClass ||
2028
// symbol != NothingClass && (symbol isSubClass ObjectClass) && !(symbol isSubClass NonNullClass);
2030
// override def isNonNull: Boolean = symbol == NonNullClass || super.isNonNull;
2031
override def kind = "ClassInfoType"
2033
override def safeToString =
2034
if (settings.debug.value || decls.size > 1)
2039
/** A nicely formatted string with newlines and such.
2041
def formattedToString: String =
2042
parents.mkString("\n with ") + (
2043
if (settings.debug.value || parents.isEmpty || (decls.elems ne null))
2044
fullyInitializeScope(decls).mkString(" {\n ", "\n ", "\n}")
2049
object ClassInfoType extends ClassInfoTypeExtractor
2051
class PackageClassInfoType(decls: Scope, clazz: Symbol)
2052
extends ClassInfoType(List(), decls, clazz)
2054
/** A class representing a constant type.
2058
abstract case class ConstantType(value: Constant) extends SingletonType with ConstantTypeApi {
2059
override def underlying: Type = value.tpe
2060
assert(underlying.typeSymbol != UnitClass)
2061
override def isTrivial: Boolean = true
2062
override def isNotNull = value.value != null
2063
override def deconst: Type = underlying
2064
override def safeToString: String =
2065
underlying.toString + "(" + value.escapedStringValue + ")"
2066
// override def isNullable: Boolean = value.value eq null
2067
// override def isNonNull: Boolean = value.value ne null
2068
override def kind = "ConstantType"
2071
final class UniqueConstantType(value: Constant) extends ConstantType(value)
2073
object ConstantType extends ConstantTypeExtractor {
2074
def apply(value: Constant) = unique(new UniqueConstantType(value))
2077
/* Syncnote: The `volatile` var and `pendingVolatiles` mutable set need not be protected
2078
* with synchronized, because they are accessed only from isVolatile, which is called only from
2081
private var volatileRecursions: Int = 0
2082
private val pendingVolatiles = new mutable.HashSet[Symbol]
2084
class ArgsTypeRef(pre0: Type, sym0: Symbol, args0: List[Type]) extends TypeRef(pre0, sym0, args0) {
2085
require(args0.nonEmpty, this)
2087
/** No unapplied type params size it has (should have) equally as many args. */
2088
override def isHigherKinded = false
2089
override def typeParams = Nil
2091
override def transform(tp: Type): Type = {
2092
// This situation arises when a typevar is encountered for which
2093
// too little information is known to determine its kind, and
2094
// it later turns out not to have kind *. See SI-4070. Only
2095
// logging it for now.
2096
if (sym.typeParams.size != args.size)
2097
log("!!! %s.transform(%s), but tparams.isEmpty and args=".format(this, tp, args))
2099
asSeenFromOwner(tp).instantiateTypeParams(sym.typeParams, args)
2102
// note: does not go through typeRef. There's no need to because
2103
// neither `pre` nor `sym` changes. And there's a performance
2104
// advantage to call TypeRef directly.
2105
override def typeConstructor = TypeRef(pre, sym, Nil)
2108
class ModuleTypeRef(pre0: Type, sym0: Symbol) extends NoArgsTypeRef(pre0, sym0) with ClassTypeRef {
2109
require(sym.isModuleClass, sym)
2110
private[this] var narrowedCache: Type = _
2111
override def isStable = true
2112
override def narrow = {
2113
if (narrowedCache eq null)
2114
narrowedCache = singleType(pre, sym.sourceModule)
2118
final override def isNotNull = true
2119
override protected def finishPrefix(rest: String) = objectPrefix + rest
2120
override def directObjectString = super.safeToString
2121
override def toLongString = toString
2122
override def safeToString = prefixString + "type"
2123
override def prefixString = if (sym.isOmittablePrefix) "" else prefix.prefixString + sym.nameString + "."
2125
class PackageTypeRef(pre0: Type, sym0: Symbol) extends ModuleTypeRef(pre0, sym0) {
2126
require(sym.isPackageClass, sym)
2127
override protected def finishPrefix(rest: String) = packagePrefix + rest
2129
class RefinementTypeRef(pre0: Type, sym0: Symbol) extends NoArgsTypeRef(pre0, sym0) with ClassTypeRef {
2130
require(sym.isRefinementClass, sym)
2132
// I think this is okay, but see #1241 (r12414), #2208, and typedTypeConstructor in Typers
2133
override protected def normalizeImpl: Type = sym.info.normalize
2134
override protected def finishPrefix(rest: String) = "" + thisInfo
2137
class NoArgsTypeRef(pre0: Type, sym0: Symbol) extends TypeRef(pre0, sym0, Nil) {
2138
// A reference (in a Scala program) to a type that has type parameters, but where the reference
2139
// does not include type arguments. Note that it doesn't matter whether the symbol refers
2140
// to a java or scala symbol, but it does matter whether it occurs in java or scala code.
2141
// TypeRefs w/o type params that occur in java signatures/code are considered raw types, and are
2142
// represented as existential types.
2143
override def isHigherKinded = typeParams.nonEmpty
2144
override def typeParams = if (isDefinitionsInitialized) sym.typeParams else sym.unsafeTypeParams
2145
private def isRaw = !phase.erasedTypes && isRawIfWithoutArgs(sym)
2147
override def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]): Type =
2148
if (isHigherKinded) {
2149
if (sameLength(formals intersect typeParams, typeParams))
2150
copyTypeRef(this, pre, sym, actuals)
2151
// partial application (needed in infer when bunching type arguments from classes and methods together)
2153
copyTypeRef(this, pre, sym, dummyArgs).instantiateTypeParams(formals, actuals)
2156
super.instantiateTypeParams(formals, actuals)
2158
override def transform(tp: Type): Type = {
2159
val res = asSeenFromOwner(tp)
2160
if (isHigherKinded && !isRaw)
2161
res.instantiateTypeParams(typeParams, dummyArgs)
2166
override def transformInfo(tp: Type): Type =
2167
appliedType(asSeenFromOwner(tp), dummyArgs)
2169
override def narrow =
2170
if (sym.isModuleClass) singleType(pre, sym.sourceModule)
2173
override def typeConstructor = this
2174
// eta-expand, subtyping relies on eta-expansion of higher-kinded types
2176
override protected def normalizeImpl: Type =
2177
if (isHigherKinded) etaExpand else super.normalizeImpl
2180
trait ClassTypeRef extends TypeRef {
2181
// !!! There are scaladoc-created symbols arriving which violate this require.
2182
// require(sym.isClass, sym)
2184
override def baseType(clazz: Symbol): Type =
2185
if (sym == clazz) this
2186
else transform(sym.info.baseType(clazz))
2189
trait NonClassTypeRef extends TypeRef {
2190
require(sym.isNonClassType, sym)
2192
/* Syncnote: These are pure caches for performance; no problem to evaluate these
2193
* several times. Hence, no need to protected with synchronzied in a mutli-threaded
2196
private var relativeInfoCache: Type = _
2197
private var memberInfoCache: Type = _
2199
private[Types] def relativeInfo = {
2200
val memberInfo = pre.memberInfo(sym)
2201
if (relativeInfoCache == null || (memberInfo ne memberInfoCache)) {
2202
memberInfoCache = memberInfo
2203
relativeInfoCache = transformInfo(memberInfo)
2208
override def baseType(clazz: Symbol): Type =
2209
if (sym == clazz) this else baseTypeOfNonClassTypeRef(this, clazz)
2212
protected def baseTypeOfNonClassTypeRef(tpe: NonClassTypeRef, clazz: Symbol) = try {
2213
basetypeRecursions += 1
2214
if (basetypeRecursions < LogPendingBaseTypesThreshold)
2215
tpe.relativeInfo.baseType(clazz)
2216
else if (pendingBaseTypes contains tpe)
2217
if (clazz == AnyClass) clazz.tpe else NoType
2220
pendingBaseTypes += tpe
2221
tpe.relativeInfo.baseType(clazz)
2223
pendingBaseTypes -= tpe
2226
basetypeRecursions -= 1
2229
trait AliasTypeRef extends NonClassTypeRef {
2230
require(sym.isAliasType, sym)
2232
override def dealias = if (typeParamsMatchArgs) betaReduce.dealias else super.dealias
2233
override def isStable = normalize.isStable
2234
override def isVolatile = normalize.isVolatile
2235
override def narrow = normalize.narrow
2236
override def thisInfo = normalize
2237
override def prefix = if (this ne normalize) normalize.prefix else pre
2238
override def termSymbol = if (this ne normalize) normalize.termSymbol else super.termSymbol
2239
override def typeSymbol = if (this ne normalize) normalize.typeSymbol else sym
2241
// beta-reduce, but don't do partial application -- cycles have been checked in typeRef
2242
override protected def normalizeImpl =
2243
if (typeParamsMatchArgs) betaReduce.normalize
2244
else if (isHigherKinded) super.normalizeImpl
2246
// if we are overriding a type alias in an erroneous way, don't just
2247
// return an ErrorType since that will result in useless error msg.
2248
// Instead let's try to recover from it and rely on refcheck reporting the correct error,
2249
// if that fails fallback to the old behaviour.
2250
val overriddenSym = sym.nextOverriddenSymbol
2251
if (overriddenSym != NoSymbol) pre.memberType(overriddenSym).normalize
2255
// isHKSubType0 introduces synthetic type params so that
2256
// betaReduce can first apply sym.info to typeArgs before calling
2257
// asSeenFrom. asSeenFrom then skips synthetic type params, which
2258
// are used to reduce HO subtyping to first-order subtyping, but
2259
// which can't be instantiated from the given prefix and class.
2261
// this crashes pos/depmet_implicit_tpbetareduce.scala
2262
// appliedType(sym.info, typeArgs).asSeenFrom(pre, sym.owner)
2263
override def betaReduce = transform(sym.info.resultType)
2265
// #3731: return sym1 for which holds: pre bound sym.name to sym and
2266
// pre1 now binds sym.name to sym1, conceptually exactly the same
2267
// symbol as sym. The selection of sym on pre must be updated to the
2268
// selection of sym1 on pre1, since sym's info was probably updated
2269
// by the TypeMap to yield a new symbol, sym1 with transformed info.
2271
override def coevolveSym(pre1: Type): Symbol =
2272
if (pre eq pre1) sym else (pre, pre1) match {
2273
// don't look at parents -- it would be an error to override alias types anyway
2274
case (RefinedType(_, _), RefinedType(_, decls1)) => decls1 lookup sym.name
2275
// TODO: is there another way a typeref's symbol can refer to a symbol defined in its pre?
2278
override def kind = "AliasTypeRef"
2281
trait AbstractTypeRef extends NonClassTypeRef {
2282
require(sym.isAbstractType, sym)
2284
/** Syncnote: Pure performance caches; no need to synchronize in multi-threaded environment
2286
private var symInfoCache: Type = _
2287
private var thisInfoCache: Type = _
2289
override def isVolatile = {
2290
// need to be careful not to fall into an infinite recursion here
2291
// because volatile checking is done before all cycles are detected.
2292
// the case to avoid is an abstract type directly or
2293
// indirectly upper-bounded by itself. See #2918
2295
volatileRecursions += 1
2296
if (volatileRecursions < LogVolatileThreshold)
2297
bounds.hi.isVolatile
2298
else if (pendingVolatiles(sym))
2299
true // we can return true here, because a cycle will be detected
2300
// here afterwards and an error will result anyway.
2303
pendingVolatiles += sym
2304
bounds.hi.isVolatile
2306
pendingVolatiles -= sym
2309
volatileRecursions -= 1
2313
override def thisInfo = {
2314
val symInfo = sym.info
2315
if (thisInfoCache == null || (symInfo ne symInfoCache)) {
2316
symInfoCache = symInfo
2317
thisInfoCache = transformInfo(symInfo) match {
2318
// If a subtyping cycle is not detected here, we'll likely enter an infinite
2319
// loop before a sensible error can be issued. SI-5093 is one example.
2320
case x: SubType if x.supertype eq this =>
2321
throw new RecoverableCyclicReference(sym)
2327
override def isStable = bounds.hi.typeSymbol isSubClass SingletonClass
2328
override def bounds = thisInfo.bounds
2329
// def transformInfo(tp: Type): Type = appliedType(tp.asSeenFrom(pre, sym.owner), typeArgsOrDummies)
2330
override protected[Types] def baseTypeSeqImpl: BaseTypeSeq = transform(bounds.hi).baseTypeSeq prepend this
2331
override def kind = "AbstractTypeRef"
2334
/** A class for named types of the form
2335
* `<prefix>.<sym.name>[args]`
2336
* Cannot be created directly; one should always use `typeRef`
2337
* for creation. (@M: Otherwise hashing breaks)
2339
* @M: a higher-kinded type is represented as a TypeRef with sym.typeParams.nonEmpty, but args.isEmpty
2341
abstract case class TypeRef(pre: Type, sym: Symbol, args: List[Type]) extends UniqueType with TypeRefApi {
2342
private var trivial: ThreeValue = UNKNOWN
2343
override def isTrivial: Boolean = {
2344
if (trivial == UNKNOWN)
2345
trivial = fromBoolean(!sym.isTypeParameter && pre.isTrivial && areTrivialTypes(args))
2348
private[reflect] var parentsCache: List[Type] = _
2349
private[reflect] var parentsPeriod = NoPeriod
2350
private[reflect] var baseTypeSeqCache: BaseTypeSeq = _
2351
private[reflect] var baseTypeSeqPeriod = NoPeriod
2352
private var normalized: Type = _
2354
//OPT specialize hashCode
2355
override final def computeHashCode = {
2356
import scala.util.hashing.MurmurHash3._
2357
val hasArgs = args.nonEmpty
2359
h = mix(h, pre.hashCode)
2360
h = mix(h, sym.hashCode)
2362
finalizeHash(mix(h, args.hashCode), 3)
2367
// @M: propagate actual type params (args) to `tp`, by replacing
2368
// formal type parameters with actual ones. If tp is higher kinded,
2369
// the "actual" type arguments are types that simply reference the
2370
// corresponding type parameters (unbound type variables)
2371
def transform(tp: Type): Type
2373
// eta-expand, subtyping relies on eta-expansion of higher-kinded types
2374
protected def normalizeImpl: Type = if (isHigherKinded) etaExpand else super.normalize
2376
// TODO: test case that is compiled in a specific order and in different runs
2377
final override def normalize: Type = {
2378
// arises when argument-dependent types are approximated (see def depoly in implicits)
2379
if (pre eq WildcardType) WildcardType
2380
else if (phase.erasedTypes) normalizeImpl
2382
if (normalized eq null)
2383
normalized = normalizeImpl
2388
override def isGround = (
2390
|| pre.isGround && args.forall(_.isGround)
2393
override def etaExpand: Type = {
2394
// must initialise symbol, see test/files/pos/ticket0137.scala
2395
val tpars = initializedTypeParams
2396
if (tpars.isEmpty) this
2397
else typeFunAnon(tpars, copyTypeRef(this, pre, sym, tpars map (_.tpeHK))) // todo: also beta-reduce?
2400
// only need to rebind type aliases, as typeRef already handles abstract types
2401
// (they are allowed to be rebound more liberally)
2402
def coevolveSym(pre1: Type): Symbol = sym
2404
//@M! use appliedType on the polytype that represents the bounds (or if aliastype, the rhs)
2405
def transformInfo(tp: Type): Type = appliedType(asSeenFromOwner(tp), args)
2407
def thisInfo = sym.info
2408
def initializedTypeParams = sym.info.typeParams
2409
def typeParamsMatchArgs = sameLength(initializedTypeParams, args)
2410
def asSeenFromOwner(tp: Type) = tp.asSeenFrom(pre, sym.owner)
2412
override def baseClasses = thisInfo.baseClasses
2413
override def baseTypeSeqDepth = baseTypeSeq.maxDepth
2414
override def isStable = (sym eq NothingClass) || (sym eq SingletonClass)
2415
override def prefix = pre
2416
override def termSymbol = super.termSymbol
2417
override def termSymbolDirect = super.termSymbol
2418
override def typeArgs = args
2419
override def typeOfThis = transform(sym.typeOfThis)
2420
override def typeSymbol = sym
2421
override def typeSymbolDirect = sym
2423
override def isNotNull =
2424
sym.isModuleClass || sym == NothingClass || (sym isNonBottomSubClass NotNullClass) || super.isNotNull
2426
override def parents: List[Type] = {
2427
val cache = parentsCache
2428
if (parentsPeriod == currentPeriod && cache != null) cache
2430
defineParentsOfTypeRef(this)
2435
override def decls: Scope = {
2437
case TypeRef(_, sym1, _) =>
2438
assert(sym1 != sym, this) // @MAT was != typeSymbol
2444
protected[Types] def baseTypeSeqImpl: BaseTypeSeq = sym.info.baseTypeSeq map transform
2446
override def baseTypeSeq: BaseTypeSeq = {
2447
val cache = baseTypeSeqCache
2448
if (baseTypeSeqPeriod == currentPeriod && cache != null && cache != undetBaseTypeSeq)
2451
defineBaseTypeSeqOfTypeRef(this)
2452
if (baseTypeSeqCache == undetBaseTypeSeq)
2453
throw new RecoverableCyclicReference(sym)
2459
// ensure that symbol is not a local copy with a name coincidence
2460
private def needsPreString = (
2461
settings.debug.value
2462
|| !shorthands(sym.fullName)
2463
|| (sym.ownersIterator exists (s => !s.isClass))
2465
private def preString = if (needsPreString) pre.prefixString else ""
2466
private def argsString = if (args.isEmpty) "" else args.mkString("[", ",", "]")
2468
def refinementString = (
2469
if (sym.isStructuralRefinement) (
2470
fullyInitializeScope(decls) filter (sym => sym.isPossibleInRefinement && sym.isPublic)
2472
mkString("{", "; ", "}")
2477
protected def finishPrefix(rest: String) = (
2478
if (sym.isInitialized && sym.isAnonymousClass && !phase.erasedTypes)
2479
parentsString(thisInfo.parents) + refinementString
2482
private def customToString = sym match {
2483
case RepeatedParamClass => args.head + "*"
2484
case ByNameParamClass => "=> " + args.head
2486
def targs = normalize.typeArgs
2488
if (isFunctionType(this)) {
2489
// Aesthetics: printing Function1 as T => R rather than (T) => R
2490
// ...but only if it's not a tuple, so ((T1, T2)) => R is distinguishable
2491
// from (T1, T2) => R.
2493
case in :: out :: Nil if !isTupleType(in) =>
2494
// A => B => C should be (A => B) => C or A => (B => C).
2495
// Also if A is byname, then we want (=> A) => B because => is right associative and => A => B
2496
// would mean => (A => B) which is a different type
2497
val in_s = if (isFunctionType(in) || isByNameParamType(in)) "(" + in + ")" else "" + in
2498
val out_s = if (isFunctionType(out)) "(" + out + ")" else "" + out
2499
in_s + " => " + out_s
2501
xs.init.mkString("(", ", ", ")") + " => " + xs.last
2504
else if (isTupleType(this))
2505
targs.mkString("(", ", ", if (hasLength(targs, 1)) ",)" else ")")
2506
else if (sym.isAliasType && prefixChain.exists(_.termSymbol.isSynthetic) && (this ne this.normalize))
2511
override def safeToString = {
2512
val custom = if (settings.debug.value) "" else customToString
2513
if (custom != "") custom
2514
else finishPrefix(preString + sym.nameString + argsString)
2516
override def prefixString = "" + (
2517
if (settings.debug.value)
2519
else if (sym.isOmittablePrefix)
2521
else if (sym.isPackageClass || sym.isPackageObjectOrClass)
2522
sym.skipPackageObject.fullName + "."
2523
else if (isStable && nme.isSingletonName(sym.name))
2524
tpnme.dropSingletonName(sym.name) + "."
2528
override def kind = "TypeRef"
2531
object TypeRef extends TypeRefExtractor {
2532
def apply(pre: Type, sym: Symbol, args: List[Type]): Type = unique({
2533
if (args.nonEmpty) {
2534
if (sym.isAliasType) new ArgsTypeRef(pre, sym, args) with AliasTypeRef
2535
else if (sym.isAbstractType) new ArgsTypeRef(pre, sym, args) with AbstractTypeRef
2536
else new ArgsTypeRef(pre, sym, args) with ClassTypeRef
2539
if (sym.isAliasType) new NoArgsTypeRef(pre, sym) with AliasTypeRef
2540
else if (sym.isAbstractType) new NoArgsTypeRef(pre, sym) with AbstractTypeRef
2541
else if (sym.isRefinementClass) new RefinementTypeRef(pre, sym)
2542
else if (sym.isPackageClass) new PackageTypeRef(pre, sym)
2543
else if (sym.isModuleClass) new ModuleTypeRef(pre, sym)
2544
else new NoArgsTypeRef(pre, sym) with ClassTypeRef
2549
protected def defineParentsOfTypeRef(tpe: TypeRef) = {
2550
val period = tpe.parentsPeriod
2551
if (period != currentPeriod) {
2552
tpe.parentsPeriod = currentPeriod
2553
if (!isValidForBaseClasses(period)) {
2554
tpe.parentsCache = tpe.thisInfo.parents map tpe.transform
2555
} else if (tpe.parentsCache == null) { // seems this can happen if things are corrupted enough, see #2641
2556
tpe.parentsCache = List(AnyClass.tpe)
2561
protected def defineBaseTypeSeqOfTypeRef(tpe: TypeRef) = {
2562
val period = tpe.baseTypeSeqPeriod
2563
if (period != currentPeriod) {
2564
tpe.baseTypeSeqPeriod = currentPeriod
2565
if (!isValidForBaseClasses(period)) {
2566
if (Statistics.canEnable) Statistics.incCounter(typerefBaseTypeSeqCount)
2567
val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, baseTypeSeqNanos) else null
2569
tpe.baseTypeSeqCache = undetBaseTypeSeq
2570
tpe.baseTypeSeqCache = tpe.baseTypeSeqImpl
2572
if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
2576
if (tpe.baseTypeSeqCache == undetBaseTypeSeq)
2577
throw new TypeError("illegal cyclic inheritance involving " + tpe.sym)
2580
/** A class representing a method type with parameters.
2581
* Note that a parameterless method is represented by a NullaryMethodType:
2583
* def m(): Int MethodType(Nil, Int)
2584
* def m: Int NullaryMethodType(Int)
2586
case class MethodType(override val params: List[Symbol],
2587
override val resultType: Type) extends Type with MethodTypeApi {
2589
private var trivial: ThreeValue = UNKNOWN
2590
override def isTrivial: Boolean = {
2591
if (trivial == UNKNOWN) trivial = fromBoolean(isTrivialResult && areTrivialParams(params))
2595
private def isTrivialResult =
2596
resultType.isTrivial && (resultType eq resultType.withoutAnnotations)
2598
private def areTrivialParams(ps: List[Symbol]): Boolean = ps match {
2600
p.tpe.isTrivial && !typesContain(paramTypes, p) && !(resultType contains p) &&
2601
areTrivialParams(rest)
2606
def isImplicit = params.nonEmpty && params.head.isImplicit
2607
def isJava = false // can we do something like for implicits? I.e. do Java methods without parameters need to be recognized?
2609
//assert(paramTypes forall (pt => !pt.typeSymbol.isImplClass))//DEBUG
2610
override def paramSectionCount: Int = resultType.paramSectionCount + 1
2612
override def paramss: List[List[Symbol]] = params :: resultType.paramss
2614
override def paramTypes = params map (_.tpe)
2616
override def boundSyms = resultType.boundSyms ++ params
2618
override def resultType(actuals: List[Type]) =
2619
if (isTrivial || phase.erasedTypes) resultType
2620
else if (/*isDependentMethodType &&*/ sameLength(actuals, params)) {
2621
val idm = new InstantiateDependentMap(params, actuals)
2622
val res = idm(resultType)
2623
existentialAbstraction(idm.existentialsNeeded, res)
2625
else existentialAbstraction(params, resultType)
2627
private var isdepmeth: ThreeValue = UNKNOWN
2628
override def isDependentMethodType: Boolean = {
2629
if (isdepmeth == UNKNOWN) isdepmeth = fromBoolean(IsDependentCollector.collect(resultType.dealias))
2630
toBoolean(isdepmeth)
2633
// implicit args can only be depended on in result type:
2634
//TODO this may be generalised so that the only constraint is dependencies are acyclic
2635
def approximate: MethodType = MethodType(params, resultApprox)
2637
override def finalResultType: Type = resultType.finalResultType
2639
override def safeToString = paramString(this) + resultType
2641
override def cloneInfo(owner: Symbol) = {
2642
val vparams = cloneSymbolsAtOwner(params, owner)
2643
copyMethodType(this, vparams, resultType.substSym(params, vparams).cloneInfo(owner))
2646
override def atOwner(owner: Symbol) =
2647
if (!allSymbolsHaveOwner(params, owner) || (resultType.atOwner(owner) ne resultType))
2652
override def kind = "MethodType"
2655
object MethodType extends MethodTypeExtractor
2657
class JavaMethodType(ps: List[Symbol], rt: Type) extends MethodType(ps, rt) {
2658
override def isJava = true
2661
case class NullaryMethodType(override val resultType: Type) extends Type with NullaryMethodTypeApi {
2662
override def isTrivial = resultType.isTrivial && (resultType eq resultType.withoutAnnotations)
2663
override def prefix: Type = resultType.prefix
2664
override def narrow: Type = resultType.narrow
2665
override def finalResultType: Type = resultType.finalResultType
2666
override def termSymbol: Symbol = resultType.termSymbol
2667
override def typeSymbol: Symbol = resultType.typeSymbol
2668
override def parents: List[Type] = resultType.parents
2669
override def decls: Scope = resultType.decls
2670
override def baseTypeSeq: BaseTypeSeq = resultType.baseTypeSeq
2671
override def baseTypeSeqDepth: Int = resultType.baseTypeSeqDepth
2672
override def baseClasses: List[Symbol] = resultType.baseClasses
2673
override def baseType(clazz: Symbol): Type = resultType.baseType(clazz)
2674
override def boundSyms = resultType.boundSyms
2675
override def isVolatile = resultType.isVolatile
2676
override def safeToString: String = "=> "+ resultType
2677
override def kind = "NullaryMethodType"
2680
object NullaryMethodType extends NullaryMethodTypeExtractor
2682
/** A type function or the type of a polymorphic value (and thus of kind *).
2684
* Before the introduction of NullaryMethodType, a polymorphic nullary method (e.g, def isInstanceOf[T]: Boolean)
2685
* used to be typed as PolyType(tps, restpe), and a monomorphic one as PolyType(Nil, restpe)
2686
* This is now: PolyType(tps, NullaryMethodType(restpe)) and NullaryMethodType(restpe)
2687
* by symmetry to MethodTypes: PolyType(tps, MethodType(params, restpe)) and MethodType(params, restpe)
2689
* Thus, a PolyType(tps, TypeRef(...)) unambiguously indicates a type function (which results from eta-expanding a type constructor alias).
2690
* Similarly, PolyType(tps, ClassInfoType(...)) is a type constructor.
2692
* A polytype is of kind * iff its resultType is a (nullary) method type.
2694
case class PolyType(override val typeParams: List[Symbol], override val resultType: Type)
2695
extends Type with PolyTypeApi {
2696
//assert(!(typeParams contains NoSymbol), this)
2697
assert(typeParams.nonEmpty, this) // used to be a marker for nullary method type, illegal now (see @NullaryMethodType)
2699
override def paramSectionCount: Int = resultType.paramSectionCount
2700
override def paramss: List[List[Symbol]] = resultType.paramss
2701
override def params: List[Symbol] = resultType.params
2702
override def paramTypes: List[Type] = resultType.paramTypes
2703
override def parents: List[Type] = resultType.parents
2704
override def decls: Scope = resultType.decls
2705
override def termSymbol: Symbol = resultType.termSymbol
2706
override def typeSymbol: Symbol = resultType.typeSymbol
2707
override def boundSyms = immutable.Set[Symbol](typeParams ++ resultType.boundSyms: _*)
2708
override def prefix: Type = resultType.prefix
2709
override def baseTypeSeq: BaseTypeSeq = resultType.baseTypeSeq
2710
override def baseTypeSeqDepth: Int = resultType.baseTypeSeqDepth
2711
override def baseClasses: List[Symbol] = resultType.baseClasses
2712
override def baseType(clazz: Symbol): Type = resultType.baseType(clazz)
2713
override def narrow: Type = resultType.narrow
2714
override def isVolatile = resultType.isVolatile
2715
override def finalResultType: Type = resultType.finalResultType
2717
/** @M: typeDefSig wraps a TypeBounds in a PolyType
2718
* to represent a higher-kinded type parameter
2719
* wrap lo&hi in polytypes to bind variables
2721
override def bounds: TypeBounds =
2722
TypeBounds(typeFun(typeParams, resultType.bounds.lo),
2723
typeFun(typeParams, resultType.bounds.hi))
2725
override def isHigherKinded = !typeParams.isEmpty
2727
override def safeToString = typeParamsString(this) + resultType
2729
override def cloneInfo(owner: Symbol) = {
2730
val tparams = cloneSymbolsAtOwner(typeParams, owner)
2731
PolyType(tparams, resultType.substSym(typeParams, tparams).cloneInfo(owner))
2734
override def atOwner(owner: Symbol) =
2735
if (!allSymbolsHaveOwner(typeParams, owner) || (resultType.atOwner(owner) ne resultType))
2740
override def kind = "PolyType"
2743
object PolyType extends PolyTypeExtractor
2745
/** A creator for existential types which flattens nested existentials.
2747
def newExistentialType(quantified: List[Symbol], underlying: Type): Type =
2748
if (quantified.isEmpty) underlying
2749
else underlying match {
2750
case ExistentialType(qs, restpe) => newExistentialType(quantified ::: qs, restpe)
2751
case _ => ExistentialType(quantified, underlying)
2754
case class ExistentialType(quantified: List[Symbol],
2755
override val underlying: Type) extends RewrappingTypeProxy with ExistentialTypeApi
2757
override protected def rewrap(newtp: Type) = existentialAbstraction(quantified, newtp)
2759
override def isTrivial = false
2760
override def isStable: Boolean = false
2761
override def bounds = TypeBounds(maybeRewrap(underlying.bounds.lo), maybeRewrap(underlying.bounds.hi))
2762
override def parents = underlying.parents map maybeRewrap
2763
override def boundSyms = quantified.toSet
2764
override def prefix = maybeRewrap(underlying.prefix)
2765
override def typeArgs = underlying.typeArgs map maybeRewrap
2766
override def params = underlying.params mapConserve { param =>
2767
val tpe1 = rewrap(param.tpeHK)
2768
if (tpe1 eq param.tpeHK) param else param.cloneSymbol.setInfo(tpe1)
2770
override def paramTypes = underlying.paramTypes map maybeRewrap
2771
override def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]) = {
2772
// maybeRewrap(underlying.instantiateTypeParams(formals, actuals))
2774
val quantified1 = new SubstTypeMap(formals, actuals) mapOver quantified
2775
val underlying1 = underlying.instantiateTypeParams(formals, actuals)
2776
if ((quantified1 eq quantified) && (underlying1 eq underlying)) this
2777
else existentialAbstraction(quantified1, underlying1.substSym(quantified, quantified1))
2780
override def baseType(clazz: Symbol) = maybeRewrap(underlying.baseType(clazz))
2781
override def baseTypeSeq = underlying.baseTypeSeq map maybeRewrap
2782
override def isHigherKinded = false
2784
override def skolemizeExistential(owner: Symbol, origin: AnyRef) =
2785
deriveType(quantified, tparam => (owner orElse tparam.owner).newExistentialSkolem(tparam, origin))(underlying)
2787
private def wildcardArgsString(qset: Set[Symbol], args: List[Type]): List[String] = args map {
2788
case TypeRef(_, sym, _) if (qset contains sym) =>
2789
"_"+sym.infoString(sym.info)
2794
/** An existential can only be printed with wildcards if:
2795
* - the underlying type is a typeref
2796
* - every quantified variable appears at most once as a type argument and
2797
* nowhere inside a type argument
2798
* - no quantified type argument contains a quantified variable in its bound
2799
* - the typeref's symbol is not itself quantified
2800
* - the prefix is not quanitified
2802
def isRepresentableWithWildcards = {
2803
val qset = quantified.toSet
2805
case TypeRef(pre, sym, args) =>
2806
def isQuantified(tpe: Type): Boolean = {
2807
(tpe exists (t => qset contains t.typeSymbol)) ||
2808
tpe.typeSymbol.isRefinementClass && (tpe.parents exists isQuantified)
2810
val (wildcardArgs, otherArgs) = args partition (arg => qset contains arg.typeSymbol)
2811
wildcardArgs.distinct == wildcardArgs &&
2812
!(otherArgs exists (arg => isQuantified(arg))) &&
2813
!(wildcardArgs exists (arg => isQuantified(arg.typeSymbol.info.bounds))) &&
2814
!(qset contains sym) &&
2820
override def safeToString: String = {
2822
val str = quantified map (_.existentialToString) mkString (" forSome { ", "; ", " }")
2823
if (settings.explaintypes.value) "(" + str + ")" else str
2826
case TypeRef(pre, sym, args) if !settings.debug.value && isRepresentableWithWildcards =>
2827
"" + TypeRef(pre, sym, Nil) + wildcardArgsString(quantified.toSet, args).mkString("[", ", ", "]")
2828
case MethodType(_, _) | NullaryMethodType(_) | PolyType(_, _) =>
2829
"(" + underlying + ")" + clauses
2831
"" + underlying + clauses
2835
override def cloneInfo(owner: Symbol) =
2836
createFromClonedSymbolsAtOwner(quantified, owner, underlying)(newExistentialType)
2838
override def atOwner(owner: Symbol) =
2839
if (!allSymbolsHaveOwner(quantified, owner)) cloneInfo(owner) else this
2841
override def kind = "ExistentialType"
2843
def withTypeVars(op: Type => Boolean): Boolean = withTypeVars(op, AnyDepth)
2845
def withTypeVars(op: Type => Boolean, depth: Int): Boolean = {
2846
val quantifiedFresh = cloneSymbols(quantified)
2847
val tvars = quantifiedFresh map (tparam => TypeVar(tparam))
2848
val underlying1 = underlying.instantiateTypeParams(quantified, tvars) // fuse subst quantified -> quantifiedFresh -> tvars
2849
op(underlying1) && {
2850
solve(tvars, quantifiedFresh, quantifiedFresh map (x => 0), false, depth) &&
2851
isWithinBounds(NoPrefix, NoSymbol, quantifiedFresh, tvars map (_.constr.inst))
2856
object ExistentialType extends ExistentialTypeExtractor
2858
/** A class containing the alternatives and type prefix of an overloaded symbol.
2859
* Not used after phase `typer`.
2861
case class OverloadedType(pre: Type, alternatives: List[Symbol]) extends Type {
2862
override def prefix: Type = pre
2863
override def safeToString =
2864
(alternatives map pre.memberType).mkString("", " <and> ", "")
2865
override def kind = "OverloadedType"
2868
def overloadedType(pre: Type, alternatives: List[Symbol]): Type =
2869
if (alternatives.tail.isEmpty) pre memberType alternatives.head
2870
else OverloadedType(pre, alternatives)
2872
/** A class remembering a type instantiation for some a set of overloaded
2873
* polymorphic symbols.
2874
* Not used after phase `typer`.
2876
case class AntiPolyType(pre: Type, targs: List[Type]) extends Type {
2877
override def safeToString =
2878
pre.toString + targs.mkString("(with type arguments ", ", ", ")");
2879
override def memberType(sym: Symbol) = appliedType(pre.memberType(sym), targs)
2880
// override def memberType(sym: Symbol) = pre.memberType(sym) match {
2881
// case PolyType(tparams, restp) =>
2882
// restp.subst(tparams, targs)
2883
// /* I don't think this is needed, as existential types close only over value types
2884
// case ExistentialType(tparams, qtpe) =>
2885
// existentialAbstraction(tparams, qtpe.memberType(sym))
2887
// case ErrorType =>
2890
override def kind = "AntiPolyType"
2893
//private var tidCount = 0 //DEBUG
2895
object HasTypeMember {
2896
def apply(name: TypeName, tp: Type): Type = {
2897
val bound = refinedType(List(WildcardType), NoSymbol)
2898
val bsym = bound.typeSymbol.newAliasType(name)
2900
bound.decls enter bsym
2903
def unapply(tp: Type): Option[(TypeName, Type)] = tp match {
2904
case RefinedType(List(WildcardType), Scope(sym)) => Some((sym.name.toTypeName, sym.info))
2910
object HasTypeParams {
2911
def unapply(tp: Type): Option[(List[Symbol], Type)] = tp match {
2912
case AnnotatedType(_, tp, _) => unapply(tp)
2913
case ExistentialType(tparams, qtpe) => Some((tparams, qtpe))
2914
case PolyType(tparams, restpe) => Some((tparams, restpe))
2920
// a TypeVar used to be a case class with only an origin and a constr
2921
// then, constr became mutable (to support UndoLog, I guess),
2922
// but pattern-matching returned the original constr0 (a bug)
2923
// now, pattern-matching returns the most recent constr
2925
@inline final def trace[T](action: String, msg: => String)(value: T): T = {
2926
if (traceTypeVars) {
2929
case str => "( " + str + " )"
2931
Console.err.println("[%10s] %-25s%s".format(action, value, s))
2936
/** Create a new TypeConstraint based on the given symbol.
2938
private def deriveConstraint(tparam: Symbol): TypeConstraint = {
2939
/** Must force the type parameter's info at this point
2940
* or things don't end well for higher-order type params.
2943
val bounds = tparam.info.bounds
2944
/** We can seed the type constraint with the type parameter
2945
* bounds as long as the types are concrete. This should lower
2946
* the complexity of the search even if it doesn't improve
2949
if (propagateParameterBoundsToTypeVars) {
2950
val exclude = bounds.isEmptyBounds || (bounds exists typeIsNonClassType)
2952
if (exclude) new TypeConstraint
2953
else TypeVar.trace("constraint", "For " + tparam.fullLocationString)(new TypeConstraint(bounds))
2955
else new TypeConstraint
2957
def untouchable(tparam: Symbol): TypeVar = createTypeVar(tparam, untouchable = true)
2958
def apply(tparam: Symbol): TypeVar = createTypeVar(tparam, untouchable = false)
2959
def apply(origin: Type, constr: TypeConstraint): TypeVar = apply(origin, constr, Nil, Nil)
2960
def apply(origin: Type, constr: TypeConstraint, args: List[Type], params: List[Symbol]): TypeVar =
2961
createTypeVar(origin, constr, args, params, untouchable = false)
2963
/** This is the only place TypeVars should be instantiated.
2965
private def createTypeVar(origin: Type, constr: TypeConstraint, args: List[Type], params: List[Symbol], untouchable: Boolean): TypeVar = {
2967
if (args.isEmpty && params.isEmpty) {
2968
if (untouchable) new TypeVar(origin, constr) with UntouchableTypeVar
2969
else new TypeVar(origin, constr) {}
2971
else if (args.size == params.size) {
2972
if (untouchable) new AppliedTypeVar(origin, constr, params zip args) with UntouchableTypeVar
2973
else new AppliedTypeVar(origin, constr, params zip args)
2975
else if (args.isEmpty) {
2976
if (untouchable) new HKTypeVar(origin, constr, params) with UntouchableTypeVar
2977
else new HKTypeVar(origin, constr, params)
2979
else throw new Error("Invalid TypeVar construction: " + ((origin, constr, args, params)))
2982
trace("create", "In " + tv.originLocation)(tv)
2984
private def createTypeVar(tparam: Symbol, untouchable: Boolean): TypeVar =
2985
createTypeVar(tparam.tpeHK, deriveConstraint(tparam), Nil, tparam.typeParams, untouchable)
2988
/** Repack existential types, otherwise they sometimes get unpacked in the
2989
* wrong location (type inference comes up with an unexpected skolem)
2991
def repackExistential(tp: Type): Type = (
2992
if (tp == NoType) tp
2993
else existentialAbstraction(existentialsInType(tp), tp)
2996
def containsExistential(tpe: Type) =
2997
tpe exists typeIsExistentiallyBound
2999
def existentialsInType(tpe: Type) =
3000
tpe withFilter typeIsExistentiallyBound map (_.typeSymbol)
3002
/** Precondition: params.nonEmpty. (args.nonEmpty enforced structurally.)
3006
_constr: TypeConstraint,
3007
override val params: List[Symbol]
3008
) extends TypeVar(_origin, _constr) {
3010
require(params.nonEmpty, this)
3011
override def isHigherKinded = true
3012
override protected def typeVarString = params.map(_.name).mkString("[", ", ", "]=>" + originName)
3015
/** Precondition: zipped params/args nonEmpty. (Size equivalence enforced structurally.)
3017
class AppliedTypeVar(
3019
_constr: TypeConstraint,
3020
zippedArgs: List[(Symbol, Type)]
3021
) extends TypeVar(_origin, _constr) {
3023
require(zippedArgs.nonEmpty, this)
3025
override def params: List[Symbol] = zippedArgs map (_._1)
3026
override def typeArgs: List[Type] = zippedArgs map (_._2)
3028
override protected def typeVarString = (
3029
zippedArgs map { case (p, a) => p.name + "=" + a } mkString (origin + "[", ", ", "]")
3033
trait UntouchableTypeVar extends TypeVar {
3034
override def untouchable = true
3035
override def isGround = true
3036
override def registerTypeEquality(tp: Type, typeVarLHS: Boolean) = tp match {
3037
case t: TypeVar if !t.untouchable =>
3038
t.registerTypeEquality(this, !typeVarLHS)
3040
super.registerTypeEquality(tp, typeVarLHS)
3042
override def registerBound(tp: Type, isLowerBound: Boolean, isNumericBound: Boolean = false): Boolean = tp match {
3043
case t: TypeVar if !t.untouchable =>
3044
t.registerBound(this, !isLowerBound, isNumericBound)
3046
super.registerBound(tp, isLowerBound, isNumericBound)
3050
/** A class representing a type variable: not used after phase `typer`.
3052
* A higher-kinded TypeVar has params (Symbols) and typeArgs (Types).
3053
* A TypeVar with nonEmpty typeArgs can only be instantiated by a higher-kinded
3054
* type that can be applied to those args. A TypeVar is much like a TypeRef,
3055
* except it has special logic for equality and subtyping.
3057
* Precondition for this class, enforced structurally: args.isEmpty && params.isEmpty.
3059
abstract case class TypeVar(
3061
var constr: TypeConstraint
3064
// We don't want case class equality/hashing as TypeVar-s are mutable,
3065
// and TypeRefs based on them get wrongly `uniqued` otherwise. See SI-7226.
3066
override def hashCode(): Int = System.identityHashCode(this)
3067
override def equals(other: Any): Boolean = this eq other.asInstanceOf[AnyRef]
3069
def untouchable = false // by other typevars
3070
override def params: List[Symbol] = Nil
3071
override def typeArgs: List[Type] = Nil
3072
override def isHigherKinded = false
3074
/** The constraint associated with the variable
3075
* Syncnote: Type variables are assumed to be used from only one
3076
* thread. They are not exposed in api.Types and are used only locally
3077
* in operations that are exposed from types. Hence, no syncing of `constr`
3078
* or `encounteredHigherLevel` or `suspended` accesses should be necessary.
3080
// var constr = constr0
3081
def instValid = constr.instValid
3082
override def isGround = instValid && constr.inst.isGround
3084
/** The variable's skolemization level */
3085
val level = skolemizationLevel
3087
/** Applies this TypeVar to type arguments, if arity matches.
3089
* Different applications of the same type constructor variable `?CC`,
3090
* e.g. `?CC[Int]` and `?CC[String]`, are modeled as distinct instances of `TypeVar`
3091
* that share a `TypeConstraint`, so that the comparisons `?CC[Int] <:< List[Int]`
3092
* and `?CC[String] <:< Iterable[String]` result in `?CC` being upper-bounded by `List` and `Iterable`.
3094
* Applying the wrong number of type args results in a TypeVar whose instance is set to `ErrorType`.
3096
def applyArgs(newArgs: List[Type]): TypeVar = (
3097
if (newArgs.isEmpty && typeArgs.isEmpty)
3099
else if (newArgs.size == params.size) {
3100
val tv = TypeVar(origin, constr, newArgs, params)
3101
TypeVar.trace("applyArgs", "In " + originLocation + ", apply args " + newArgs.mkString(", ") + " to " + originName)(tv)
3104
TypeVar(typeSymbol).setInst(ErrorType)
3106
// newArgs.length may differ from args.length (could've been empty before)
3108
// !!! @PP - I need an example of this, since this exception never triggers
3109
// even though I am requiring the size match.
3111
// example: when making new typevars, you start out with C[A], then you replace C by ?C, which should yield ?C[A], then A by ?A, ?C[?A]
3112
// we need to track a TypeVar's arguments, and map over them (see TypeMap::mapOver)
3113
// TypeVars get applied to different arguments over time (in asSeenFrom)
3114
// -- see pos/tcpoly_infer_implicit_tuplewrapper.scala
3115
// thus: make new TypeVar's for every application of a TV to args,
3116
// inference may generate several TypeVar's for a single type parameter that must be inferred,
3117
// only one of them is in the set of tvars that need to be solved, but
3118
// they share the same TypeConstraint instance
3120
// When comparing to types containing skolems, remember the highest level
3121
// of skolemization. If that highest level is higher than our initial
3122
// skolemizationLevel, we can't re-use those skolems as the solution of this
3123
// typevar, which means we'll need to repack our constr.inst into a fresh
3125
// were we compared to skolems at a higher skolemizationLevel?
3126
// EXPERIMENTAL: value will not be considered unless enableTypeVarExperimentals is true
3127
// see SI-5729 for why this is still experimental
3128
private var encounteredHigherLevel = false
3129
private def shouldRepackType = enableTypeVarExperimentals && encounteredHigherLevel
3131
// <region name="constraint mutators + undoLog">
3132
// invariant: before mutating constr, save old state in undoLog
3133
// (undoLog is used to reset constraints to avoid piling up unrelated ones)
3134
def setInst(tp: Type): this.type = {
3135
// assert(!(tp containsTp this), this)
3137
// if we were compared against later typeskolems, repack the existential,
3138
// because skolems are only compatible if they were created at the same level
3139
val res = if (shouldRepackType) repackExistential(tp) else tp
3140
constr.inst = TypeVar.trace("setInst", "In " + originLocation + ", " + originName + "=" + res)(res)
3144
def addLoBound(tp: Type, isNumericBound: Boolean = false) {
3145
assert(tp != this, tp) // implies there is a cycle somewhere (?)
3146
//println("addLoBound: "+(safeToString, debugString(tp))) //DEBUG
3148
constr.addLoBound(tp, isNumericBound)
3151
def addHiBound(tp: Type, isNumericBound: Boolean = false) {
3152
// assert(tp != this)
3153
//println("addHiBound: "+(safeToString, debugString(tp))) //DEBUG
3155
constr.addHiBound(tp, isNumericBound)
3159
// ignore subtyping&equality checks while true -- see findMember
3160
private[Types] var suspended = false
3162
/** Called when a TypeVar is involved in a subtyping check. Result is whether
3163
* this TypeVar could plausibly be a [super/sub]type of argument `tp` and if so,
3164
* tracks tp as a [lower/upper] bound of this TypeVar.
3166
* if (isLowerBound) this typevar could be a subtype, track tp as a lower bound
3167
* if (!isLowerBound) this typevar could be a supertype, track tp as an upper bound
3169
* If isNumericBound is true, the subtype check is performed with weak_<:< instead of <:<.
3171
def registerBound(tp: Type, isLowerBound: Boolean, isNumericBound: Boolean = false): Boolean = {
3172
// println("regBound: "+(safeToString, debugString(tp), isLowerBound)) //@MDEBUG
3176
// side effect: adds the type to upper or lower bounds
3177
def addBound(tp: Type) {
3178
if (isLowerBound) addLoBound(tp, isNumericBound)
3179
else addHiBound(tp, isNumericBound)
3181
// swaps the arguments if it's an upper bound
3182
def checkSubtype(tp1: Type, tp2: Type) = {
3183
val lhs = if (isLowerBound) tp1 else tp2
3184
val rhs = if (isLowerBound) tp2 else tp1
3186
if (isNumericBound) lhs weak_<:< rhs
3190
/** Simple case: type arguments can be ignored, because either this typevar has
3191
* no type parameters, or we are comparing to Any/Nothing.
3193
* The latter condition is needed because HK unification is limited to constraints of the shape
3195
* TC1[T1,..., TN] <: TC2[T'1,...,T'N]
3197
* which would preclude the following important constraints:
3199
* Nothing <: ?TC[?T]
3204
val sym = tp.typeSymbol
3205
if (sym == NothingClass || sym == AnyClass) { // kind-polymorphic
3206
// SI-7126 if we register some type alias `T=Any`, we can later end
3207
// with malformed types like `T[T]` during type inference in
3208
// `handlePolymorphicCall`. No such problem if we register `Any`.
3211
} else if (params.isEmpty) {
3217
/** Full case: involving a check of the form
3219
* TC1[T1,..., TN] <: TC2[T'1,...,T'N]
3221
* Checks subtyping of higher-order type vars, and uses variances as defined in the
3222
* type parameter we're trying to infer (the result will be sanity-checked later).
3224
def unifyFull(tpe: Type): Boolean = {
3225
def unifySpecific(tp: Type) = {
3226
sameLength(typeArgs, tp.typeArgs) && {
3227
val lhs = if (isLowerBound) tp.typeArgs else typeArgs
3228
val rhs = if (isLowerBound) typeArgs else tp.typeArgs
3229
// This is a higher-kinded type var with same arity as tp.
3230
// If so (see SI-7517), side effect: adds the type constructor itself as a bound.
3231
isSubArgs(lhs, rhs, params, AnyDepth) && { addBound(tp.typeConstructor); true }
3234
// The type with which we can successfully unify can be hidden
3235
// behind singleton types and type aliases.
3236
tpe.dealiasWidenChain exists unifySpecific
3239
// There's a <: test taking place right now, where tp is a concrete type and this is a typevar
3240
// attempting to satisfy that test. Either the test will be unsatisfiable, in which case
3241
// registerBound will return false; or the upper or lower bounds of this type var will be
3242
// supplemented with the type being tested against.
3244
// Eventually the types which have accumulated in the upper and lower bounds will be lubbed
3245
// (resp. glbbed) to instantiate the typevar.
3247
// The only types which are eligible for unification are those with the same number of
3248
// typeArgs as this typevar, or Any/Nothing, which are kind-polymorphic. For the upper bound,
3249
// any parent or base type of `tp` may be tested here (leading to a corresponding relaxation
3250
// in the upper bound.) The universe of possible glbs, being somewhat more infinite, is not
3251
// addressed here: all lower bounds are retained and their intersection calculated when the
3252
// bounds are solved.
3254
// In a side-effect free universe, checking tp and tp.parents beofre checking tp.baseTypeSeq
3255
// would be pointless. In this case, each check we perform causes us to lose specificity: in
3256
// the end the best we'll do is the least specific type we tested against, since the typevar
3257
// does not see these checks as "probes" but as requirements to fulfill.
3258
// TODO: can the `suspended` flag be used to poke around without leaving a trace?
3260
// So the strategy used here is to test first the type, then the direct parents, and finally
3261
// to fall back on the individual base types. This warrants eventual re-examination.
3263
// AM: I think we could use the `suspended` flag to avoid side-effecting during unification
3264
if (suspended) // constraint accumulation is disabled
3265
checkSubtype(tp, origin)
3266
else if (constr.instValid) // type var is already set
3267
checkSubtype(tp, constr.inst)
3268
else isRelatable(tp) && {
3269
unifySimple || unifyFull(tp) || (
3270
// only look harder if our gaze is oriented toward Any
3272
(tp.parents exists unifyFull) || (
3273
// @PP: Is it going to be faster to filter out the parents we just checked?
3274
// That's what's done here but I'm not sure it matters.
3275
tp.baseTypeSeq.toList.tail filterNot (tp.parents contains _) exists unifyFull
3282
def registerTypeEquality(tp: Type, typeVarLHS: Boolean): Boolean = {
3283
// println("regTypeEq: "+(safeToString, debugString(tp), tp.getClass, if (typeVarLHS) "in LHS" else "in RHS", if (suspended) "ZZ" else if (constr.instValid) "IV" else "")) //@MDEBUG
3284
// println("constr: "+ constr)
3285
def checkIsSameType(tp: Type) =
3286
if(typeVarLHS) constr.inst =:= tp
3287
else tp =:= constr.inst
3289
if (suspended) tp =:= origin
3290
else if (constr.instValid) checkIsSameType(tp)
3291
else isRelatable(tp) && {
3292
val newInst = wildcardToTypeVarMap(tp)
3293
(constr isWithinBounds newInst) && { setInst(tp); true }
3298
* `?A.T =:= tp` is rewritten as the constraint `?A <: {type T = tp}`
3300
* TODO: make these constraints count (incorporate them into implicit search in `applyImplicitArgs`)
3301
* (`T` corresponds to @param sym)
3303
def registerTypeSelection(sym: Symbol, tp: Type): Boolean = {
3304
registerBound(HasTypeMember(sym.name.toTypeName, tp), false)
3307
private def isSkolemAboveLevel(tp: Type) = tp.typeSymbol match {
3308
case ts: TypeSkolem => ts.level > level
3311
// side-effects encounteredHigherLevel
3312
private def containsSkolemAboveLevel(tp: Type) =
3313
(tp exists isSkolemAboveLevel) && { encounteredHigherLevel = true ; true }
3315
/** Can this variable be related in a constraint to type `tp`?
3316
* This is not the case if `tp` contains type skolems whose
3317
* skolemization level is higher than the level of this variable.
3319
def isRelatable(tp: Type) = (
3320
shouldRepackType // short circuit if we already know we've seen higher levels
3321
|| !containsSkolemAboveLevel(tp) // side-effects tracking boolean
3322
|| enableTypeVarExperimentals // -Xexperimental: always say we're relatable, track consequences
3325
override def normalize: Type = (
3326
if (constr.instValid) constr.inst
3327
// get here when checking higher-order subtyping of the typevar by itself
3328
// TODO: check whether this ever happens?
3329
else if (isHigherKinded) logResult("Normalizing HK $this")(typeFun(params, applyArgs(params map (_.typeConstructor))))
3330
else super.normalize
3332
override def typeSymbol = origin.typeSymbol
3333
override def isStable = origin.isStable
3334
override def isVolatile = origin.isVolatile
3336
private def tparamsOfSym(sym: Symbol) = sym.info match {
3337
case PolyType(tparams, _) if tparams.nonEmpty =>
3338
tparams map (_.defString) mkString("[", ",", "]")
3341
def originName = origin.typeSymbolDirect.decodedName
3342
def originLocation = {
3343
val sym = origin.typeSymbolDirect
3344
val encl = sym.owner.logicallyEnclosingMember
3346
// This should display somewhere between one and three
3347
// things which enclose the origin: at most, a class, a
3348
// a method, and a term. At least, a class.
3350
Some(encl.enclClass),
3351
if (encl.isMethod) Some(encl) else None,
3352
if (sym.owner.isTerm && (sym.owner != encl)) Some(sym.owner) else None
3353
).flatten map (s => s.decodedName + tparamsOfSym(s)) mkString "#"
3355
private def levelString = if (settings.explaintypes.value) level else ""
3356
protected def typeVarString = originName
3357
override def safeToString = (
3358
if ((constr eq null) || (constr.inst eq null)) "TVar<" + originName + "=null>"
3359
else if (constr.inst ne NoType) "=?" + constr.inst
3360
else (if(untouchable) "!?" else "?") + levelString + originName
3362
override def kind = "TypeVar"
3364
def cloneInternal = {
3365
// cloning a suspended type variable when it's suspended will cause the clone
3366
// to never be resumed with the current implementation
3367
assert(!suspended, this)
3368
TypeVar.trace("clone", originLocation)(
3369
TypeVar(origin, constr.cloneInternal, typeArgs, params) // @M TODO: clone args/params?
3374
/** A type carrying some annotations. Created by the typechecker
3375
* when eliminating ''Annotated'' trees (see typedAnnotated).
3377
* @param annotations the list of annotations on the type
3378
* @param underlying the type without the annotation
3379
* @param selfsym a "self" symbol with type `underlying`;
3380
* only available if -Yself-in-annots is turned on. Can be `NoSymbol`
3381
* if it is not used.
3383
case class AnnotatedType(override val annotations: List[AnnotationInfo],
3384
override val underlying: Type,
3385
override val selfsym: Symbol)
3386
extends RewrappingTypeProxy with AnnotatedTypeApi {
3388
assert(!annotations.isEmpty, "" + underlying)
3390
override protected def rewrap(tp: Type) = copy(underlying = tp)
3392
override def isTrivial: Boolean = underlying.isTrivial && annotations.forall(_.isTrivial)
3394
override def safeToString = annotations.mkString(underlying + " @", " @", "")
3396
override def filterAnnotations(p: AnnotationInfo => Boolean): Type = {
3397
val (yes, no) = annotations partition p
3398
if (yes.isEmpty) underlying
3399
else if (no.isEmpty) this
3400
else copy(annotations = yes)
3402
override def setAnnotations(annots: List[AnnotationInfo]): Type =
3403
if (annots.isEmpty) underlying
3404
else copy(annotations = annots)
3406
/** Add a number of annotations to this type */
3407
override def withAnnotations(annots: List[AnnotationInfo]): Type =
3408
if (annots.isEmpty) this
3409
else copy(annots ::: this.annotations)
3411
/** Remove any annotations from this type.
3412
* TODO - is it allowed to nest AnnotatedTypes? If not then let's enforce
3413
* that at creation. At the moment if they do ever turn up nested this
3414
* recursively calls withoutAnnotations.
3416
override def withoutAnnotations = underlying.withoutAnnotations
3418
/** Set the self symbol */
3419
override def withSelfsym(sym: Symbol) = copy(selfsym = sym)
3421
/** Drop the annotations on the bounds, unless the low and high
3422
* bounds are exactly tp.
3424
override def bounds: TypeBounds = underlying.bounds match {
3425
case TypeBounds(_: this.type, _: this.type) => TypeBounds(this, this)
3429
// ** Replace formal type parameter symbols with actual type arguments. * /
3430
override def instantiateTypeParams(formals: List[Symbol], actuals: List[Type]) = {
3431
val annotations1 = annotations.map(info => AnnotationInfo(info.atp.instantiateTypeParams(
3432
formals, actuals), info.args, info.assocs).setPos(info.pos))
3433
val underlying1 = underlying.instantiateTypeParams(formals, actuals)
3434
if ((annotations1 eq annotations) && (underlying1 eq underlying)) this
3435
else AnnotatedType(annotations1, underlying1, selfsym)
3438
/** Return the base type sequence of tp, dropping the annotations, unless the base type sequence of tp
3439
* is precisely tp itself. */
3440
override def baseTypeSeq: BaseTypeSeq = {
3441
val oftp = underlying.baseTypeSeq
3442
if ((oftp.length == 1) && (oftp(0) eq underlying))
3443
baseTypeSingletonSeq(this)
3448
override def kind = "AnnotatedType"
3451
/** Creator for AnnotatedTypes. It returns the underlying type if annotations.isEmpty
3452
* rather than walking into the assertion.
3454
def annotatedType(annots: List[AnnotationInfo], underlying: Type, selfsym: Symbol = NoSymbol): Type =
3455
if (annots.isEmpty) underlying
3456
else AnnotatedType(annots, underlying, selfsym)
3458
object AnnotatedType extends AnnotatedTypeExtractor
3460
/** A class representing types with a name. When an application uses
3461
* named arguments, the named argument types for calling isApplicable
3462
* are represented as NamedType.
3464
case class NamedType(name: Name, tp: Type) extends Type {
3465
override def safeToString: String = name.toString +": "+ tp
3468
/** A De Bruijn index referring to a previous type argument. Only used
3469
* as a serialization format.
3471
case class DeBruijnIndex(level: Int, idx: Int, args: List[Type]) extends Type {
3472
override def safeToString: String = "De Bruijn index("+level+","+idx+")"
3475
/** A binder defining data associated with De Bruijn indices. Only used
3476
* as a serialization format.
3478
case class DeBruijnBinder(pnames: List[Name], ptypes: List[Type], restpe: Type) extends Type {
3479
override def safeToString = {
3480
val kind = if (pnames.head.isTypeName) "poly" else "method"
3481
"De Bruijn "+kind+"("+(pnames mkString ",")+";"+(ptypes mkString ",")+";"+restpe+")"
3485
/** A temporary type representing the erasure of a user-defined value type.
3486
* Created during phase erasure, eliminated again in posterasure.
3488
* @param original The underlying type before erasure
3490
abstract case class ErasedValueType(original: TypeRef) extends UniqueType {
3491
override def safeToString = "ErasedValueType("+original+")"
3494
final class UniqueErasedValueType(original: TypeRef) extends ErasedValueType(original)
3496
object ErasedValueType {
3497
def apply(original: TypeRef): Type = {
3498
assert(original.sym ne NoSymbol, "ErasedValueType over NoSymbol")
3499
unique(new UniqueErasedValueType(original))
3503
/** A class representing an as-yet unevaluated type.
3505
abstract class LazyType extends Type {
3506
override def isComplete: Boolean = false
3507
override def complete(sym: Symbol)
3508
override def safeToString = "<?>"
3509
override def kind = "LazyType"
3512
/** A marker trait representing an as-yet unevaluated type
3513
* which doesn't assign flags to the underlying symbol.
3515
trait FlagAgnosticCompleter extends LazyType
3517
/** A marker trait representing an as-yet unevaluated type
3518
* which assigns flags to the underlying symbol.
3520
trait FlagAssigningCompleter extends LazyType
3522
abstract class LazyPolyType(override val typeParams: List[Symbol]) extends LazyType {
3523
override def safeToString =
3524
(if (typeParams.isEmpty) "" else typeParamsString(this)) + super.safeToString
3527
// def mkLazyType(tparams: Symbol*)(f: Symbol => Unit): LazyType = (
3528
// if (tparams.isEmpty) new LazyType { override def complete(sym: Symbol) = f(sym) }
3529
// else new LazyPolyType(tparams.toList) { override def complete(sym: Symbol) = f(sym) }
3532
// Creators ---------------------------------------------------------------
3534
/** Rebind symbol `sym` to an overriding member in type `pre`. */
3535
private def rebind(pre: Type, sym: Symbol): Symbol = {
3536
if (!sym.isOverridableMember || sym.owner == pre.typeSymbol) sym
3537
else pre.nonPrivateMember(sym.name).suchThat(sym => sym.isType || sym.isStable) orElse sym
3540
/** Convert a `super` prefix to a this-type if `sym` is abstract or final. */
3541
private def removeSuper(tp: Type, sym: Symbol): Type = tp match {
3542
case SuperType(thistp, _) =>
3543
if (sym.isEffectivelyFinal || sym.isDeferred) thistp
3549
/** The canonical creator for single-types */
3550
def singleType(pre: Type, sym: Symbol): Type = {
3551
if (phase.erasedTypes)
3553
else if (sym.isRootPackage)
3554
ThisType(sym.moduleClass)
3556
var sym1 = rebind(pre, sym)
3557
val pre1 = removeSuper(pre, sym1)
3558
if (pre1 ne pre) sym1 = rebind(pre1, sym1)
3559
SingleType(pre1, sym1)
3563
/** the canonical creator for a refined type with a given scope */
3564
def refinedType(parents: List[Type], owner: Symbol, decls: Scope, pos: Position): Type = {
3565
if (phase.erasedTypes)
3566
if (parents.isEmpty) ObjectClass.tpe else parents.head
3568
val clazz = owner.newRefinementClass(pos)
3569
val result = RefinedType(parents, decls, clazz)
3570
clazz.setInfo(result)
3575
/** The canonical creator for a refined type with an initially empty scope.
3577
* @param parents ...
3581
def refinedType(parents: List[Type], owner: Symbol): Type =
3582
refinedType(parents, owner, newScope, owner.pos)
3584
def copyRefinedType(original: RefinedType, parents: List[Type], decls: Scope) =
3585
if ((parents eq original.parents) && (decls eq original.decls)) original
3587
val owner = if (original.typeSymbol == NoSymbol) NoSymbol else original.typeSymbol.owner
3588
val result = refinedType(parents, owner)
3589
val syms1 = decls.toList
3591
result.decls.enter(sym.cloneSymbol(result.typeSymbol))
3592
val syms2 = result.decls.toList
3593
val resultThis = result.typeSymbol.thisType
3595
sym modifyInfo (_ substThisAndSym(original.typeSymbol, resultThis, syms1, syms2))
3600
/** The canonical creator for typerefs
3601
* todo: see how we can clean this up a bit
3603
def typeRef(pre: Type, sym: Symbol, args: List[Type]): Type = {
3604
// type alias selections are rebound in TypeMap ("coevolved",
3605
// actually -- see #3731) e.g., when type parameters that are
3606
// referenced by the alias are instantiated in the prefix. See
3607
// pos/depmet_rebind_typealias.
3609
val sym1 = if (sym.isAbstractType) rebind(pre, sym) else sym
3610
// don't expand cyclical type alias
3611
// we require that object is initialized, thus info.typeParams instead of typeParams.
3612
if (sym1.isAliasType && sameLength(sym1.info.typeParams, args) && !sym1.lockOK)
3613
throw new RecoverableCyclicReference(sym1)
3615
val pre1 = pre match {
3616
case x: SuperType if sym1.isEffectivelyFinal || sym1.isDeferred =>
3620
if (pre eq pre1) TypeRef(pre, sym1, args)
3621
else if (sym1.isAbstractType && !sym1.isClass) typeRef(pre1, rebind(pre1, sym1), args)
3622
else typeRef(pre1, sym1, args)
3625
// Optimization to avoid creating unnecessary new typerefs.
3626
def copyTypeRef(tp: Type, pre: Type, sym: Symbol, args: List[Type]): Type = tp match {
3627
case TypeRef(pre0, sym0, _) if pre == pre0 && sym0.name == sym.name =>
3628
if (sym.isAliasType && sameLength(sym.info.typeParams, args) && !sym.lockOK)
3629
throw new RecoverableCyclicReference(sym)
3631
TypeRef(pre, sym, args)
3633
typeRef(pre, sym, args)
3636
/** The canonical creator for implicit method types */
3637
def JavaMethodType(params: List[Symbol], resultType: Type): JavaMethodType =
3638
new JavaMethodType(params, resultType) // don't unique this!
3640
/** Create a new MethodType of the same class as tp, i.e. keep JavaMethodType */
3641
def copyMethodType(tp: Type, params: List[Symbol], restpe: Type): Type = tp match {
3642
case _: JavaMethodType => JavaMethodType(params, restpe)
3643
case _ => MethodType(params, restpe)
3646
/** A creator for intersection type where intersections of a single type are
3647
* replaced by the type itself, and repeated parent classes are merged.
3649
* !!! Repeated parent classes are not merged - is this a bug in the
3650
* comment or in the code?
3652
def intersectionType(tps: List[Type], owner: Symbol): Type = tps match {
3653
case tp :: Nil => tp
3654
case _ => refinedType(tps, owner)
3656
/** A creator for intersection type where intersections of a single type are
3657
* replaced by the type itself.
3659
def intersectionType(tps: List[Type]): Type = tps match {
3660
case tp :: Nil => tp
3661
case _ => refinedType(tps, commonOwner(tps))
3664
/**** This implementation to merge parents was checked in in commented-out
3665
form and has languished unaltered for five years. I think we should
3668
def merge(tps: List[Type]): List[Type] = tps match {
3670
val tps1a = tps1 filter (_.typeSymbol.==(tp.typeSymbol))
3671
val tps1b = tps1 filter (_.typeSymbol.!=(tp.typeSymbol))
3672
mergePrefixAndArgs(tps1a, -1) match {
3673
case Some(tp1) => tp1 :: merge(tps1b)
3674
case None => throw new MalformedType(
3675
"malformed type: "+refinedType(tps, owner)+" has repeated parent class "+
3676
tp.typeSymbol+" with incompatible prefixes or type arguments")
3680
refinedType(merge(tps), owner)
3683
/** A creator for type applications */
3684
def appliedType(tycon: Type, args: List[Type]): Type = {
3686
return tycon //@M! `if (args.isEmpty) tycon' is crucial (otherwise we create new types in phases after typer and then they don't get adapted (??))
3688
/** Disabled - causes cycles in tcpoly tests. */
3689
if (false && isDefinitionsInitialized) {
3690
assert(isUseableAsTypeArgs(args), {
3691
val tapp_s = s"""$tycon[${args mkString ", "}]"""
3692
val arg_s = args filterNot isUseableAsTypeArg map (t => t + "/" + t.getClass) mkString ", "
3693
s"$tapp_s includes illegal type argument $arg_s"
3698
case TypeRef(pre, sym @ (NothingClass|AnyClass), _) => copyTypeRef(tycon, pre, sym, Nil) //@M drop type args to Any/Nothing
3699
case TypeRef(pre, sym, _) => copyTypeRef(tycon, pre, sym, args)
3700
case PolyType(tparams, restpe) => restpe.instantiateTypeParams(tparams, args)
3701
case ExistentialType(tparams, restpe) => newExistentialType(tparams, appliedType(restpe, args))
3702
case st: SingletonType => appliedType(st.widen, args) // @M TODO: what to do? see bug1
3703
case RefinedType(parents, decls) => RefinedType(parents map (appliedType(_, args)), decls) // MO to AM: please check
3704
case TypeBounds(lo, hi) => TypeBounds(appliedType(lo, args), appliedType(hi, args))
3705
case tv@TypeVar(_, _) => tv.applyArgs(args)
3706
case AnnotatedType(annots, underlying, self) => AnnotatedType(annots, appliedType(underlying, args), self)
3707
case ErrorType => tycon
3708
case WildcardType => tycon // needed for neg/t0226
3709
case _ => abort(debugString(tycon))
3713
/** Very convenient. */
3714
def appliedType(tyconSym: Symbol, args: Type*): Type =
3715
appliedType(tyconSym.typeConstructor, args.toList)
3717
/** A creator for existential types where the type arguments,
3718
* rather than being applied directly, are interpreted as the
3719
* upper bounds of unknown types. For instance if the type argument
3720
* list given is List(AnyRefClass), the resulting type would be
3721
* e.g. Set[_ <: AnyRef] rather than Set[AnyRef] .
3723
def appliedTypeAsUpperBounds(tycon: Type, args: List[Type]): Type = {
3725
case TypeRef(pre, sym, _) if sameLength(sym.typeParams, args) =>
3726
val eparams = typeParamsToExistentials(sym)
3727
val bounds = args map (TypeBounds upper _)
3728
foreach2(eparams, bounds)(_ setInfo _)
3730
newExistentialType(eparams, typeRef(pre, sym, eparams map (_.tpe)))
3732
appliedType(tycon, args)
3736
/** A creator and extractor for type parameterizations that strips empty type parameter lists.
3737
* Use this factory method to indicate the type has kind * (it's a polymorphic value)
3738
* until we start tracking explicit kinds equivalent to typeFun (except that the latter requires tparams nonEmpty).
3740
* PP to AM: I've co-opted this for where I know tparams may well be empty, and
3741
* expecting to get back `tpe` in such cases. Re being "forgiving" below,
3742
* can we instead say this is the canonical creator for polyTypes which
3743
* may or may not be poly? (It filched the standard "canonical creator" name.)
3745
object GenPolyType {
3746
def apply(tparams: List[Symbol], tpe: Type): Type = {
3748
case MethodType(_, _) =>
3749
assert(tparams forall (_.isInvariant), "Trying to create a method with variant type parameters: " + ((tparams, tpe)))
3752
if (tparams.nonEmpty) typeFun(tparams, tpe)
3753
else tpe // it's okay to be forgiving here
3755
def unapply(tpe: Type): Option[(List[Symbol], Type)] = tpe match {
3756
case PolyType(tparams, restpe) => Some((tparams, restpe))
3757
case _ => Some((Nil, tpe))
3760
def genPolyType(params: List[Symbol], tpe: Type): Type = GenPolyType(params, tpe)
3762
@deprecated("use genPolyType(...) instead", "2.10.0")
3763
def polyType(params: List[Symbol], tpe: Type): Type = GenPolyType(params, tpe)
3765
/** A creator for anonymous type functions, where the symbol for the type function still needs to be created.
3768
* 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
3769
* higher-order subtyping expects eta-expansion of type constructors that arise from a class; here, the type params are owned by that class, but is that the right thing to do?
3771
def typeFunAnon(tps: List[Symbol], body: Type): Type = typeFun(tps, body)
3773
/** A creator for a type functions, assuming the type parameters tps already have the right owner. */
3774
def typeFun(tps: List[Symbol], body: Type): Type = PolyType(tps, body)
3776
/** A creator for existential types. This generates:
3778
* tpe1 where { tparams }
3780
* where `tpe1` is the result of extrapolating `tpe` with respect to `tparams`.
3781
* Extrapolating means that type variables in `tparams` occurring
3782
* in covariant positions are replaced by upper bounds, (minus any
3783
* SingletonClass markers), type variables in `tparams` occurring in
3784
* contravariant positions are replaced by upper bounds, provided the
3785
* resulting type is legal with regard to stability, and does not contain any type
3786
* variable in `tparams`.
3788
* The abstraction drops all type parameters that are not directly or
3789
* indirectly referenced by type `tpe1`. If there are no remaining type
3790
* parameters, simply returns result type `tpe`.
3792
def existentialAbstraction(tparams: List[Symbol], tpe0: Type): Type =
3793
if (tparams.isEmpty) tpe0
3795
val tpe = normalizeAliases(tpe0)
3796
val tpe1 = new ExistentialExtrapolation(tparams) extrapolate tpe
3797
var tparams0 = tparams
3798
var tparams1 = tparams0 filter tpe1.contains
3800
while (tparams1 != tparams0) {
3802
tparams1 = tparams filter { p =>
3803
tparams1 exists { p1 => p1 == p || (p1.info contains p) }
3806
newExistentialType(tparams1, tpe1)
3809
/** Normalize any type aliases within this type (@see Type#normalize).
3810
* Note that this depends very much on the call to "normalize", not "dealias",
3811
* so it is no longer carries the too-stealthy name "deAlias".
3813
object normalizeAliases extends TypeMap {
3814
def apply(tp: Type): Type = tp match {
3815
case TypeRef(_, sym, _) if sym.isAliasType =>
3816
def msg = if (tp.isHigherKinded) s"Normalizing type alias function $tp" else s"Dealiasing type alias $tp"
3817
mapOver(logResult(msg)(tp.normalize))
3818
case _ => mapOver(tp)
3822
/** Remove any occurrence of type <singleton> from this type and its parents */
3823
object dropSingletonType extends TypeMap {
3824
def apply(tp: Type): Type = {
3826
case TypeRef(_, SingletonClass, _) =>
3828
case tp1 @ RefinedType(parents, decls) =>
3829
parents filter (_.typeSymbol != SingletonClass) match {
3830
case Nil => AnyClass.tpe
3831
case p :: Nil if decls.isEmpty => mapOver(p)
3832
case ps => mapOver(copyRefinedType(tp1, ps, decls))
3840
/** Substitutes the empty scope for any non-empty decls in the type. */
3841
object dropAllRefinements extends TypeMap {
3842
def apply(tp: Type): Type = tp match {
3843
case rt @ RefinedType(parents, decls) if !decls.isEmpty =>
3844
mapOver(copyRefinedType(rt, parents, EmptyScope))
3845
case ClassInfoType(parents, decls, clazz) if !decls.isEmpty =>
3846
mapOver(ClassInfoType(parents, EmptyScope, clazz))
3852
/** Type with all top-level occurrences of abstract types replaced by their bounds */
3853
def abstractTypesToBounds(tp: Type): Type = tp match { // @M don't normalize here (compiler loops on pos/bug1090.scala )
3854
case TypeRef(_, sym, _) if sym.isAbstractType =>
3855
abstractTypesToBounds(tp.bounds.hi)
3856
case TypeRef(_, sym, _) if sym.isAliasType =>
3857
abstractTypesToBounds(tp.normalize)
3858
case rtp @ RefinedType(parents, decls) =>
3859
copyRefinedType(rtp, parents mapConserve abstractTypesToBounds, decls)
3860
case AnnotatedType(_, underlying, _) =>
3861
abstractTypesToBounds(underlying)
3866
// Set to true for A* => Seq[A]
3867
// (And it will only rewrite A* in method result types.)
3868
// This is the pre-existing behavior.
3869
// Or false for Seq[A] => Seq[A]
3870
// (It will rewrite A* everywhere but method parameters.)
3871
// This is the specified behavior.
3872
protected def etaExpandKeepsStar = false
3874
/** Turn any T* types into Seq[T] except when
3875
* in method parameter position.
3877
object dropRepeatedParamType extends TypeMap {
3878
def apply(tp: Type): Type = tp match {
3879
case MethodType(params, restpe) =>
3880
// Not mapping over params
3881
val restpe1 = apply(restpe)
3882
if (restpe eq restpe1) tp
3883
else MethodType(params, restpe1)
3884
case TypeRef(_, RepeatedParamClass, arg :: Nil) =>
3887
if (etaExpandKeepsStar) tp else mapOver(tp)
3891
object toDeBruijn extends TypeMap {
3892
private var paramStack: List[List[Symbol]] = Nil
3893
def mkDebruijnBinder(params: List[Symbol], restpe: Type) = {
3894
paramStack = params :: paramStack
3896
DeBruijnBinder(params map (_.name), params map (p => this(p.info)), this(restpe))
3897
} finally paramStack = paramStack.tail
3899
def apply(tp: Type): Type = tp match {
3900
case PolyType(tparams, restpe) =>
3901
mkDebruijnBinder(tparams, restpe)
3902
case MethodType(params, restpe) =>
3903
mkDebruijnBinder(params, restpe)
3904
case TypeRef(NoPrefix, sym, args) =>
3905
val level = paramStack indexWhere (_ contains sym)
3906
if (level < 0) mapOver(tp)
3907
else DeBruijnIndex(level, paramStack(level) indexOf sym, args mapConserve this)
3913
def fromDeBruijn(owner: Symbol) = new TypeMap {
3914
private var paramStack: List[List[Symbol]] = Nil
3915
def apply(tp: Type): Type = tp match {
3916
case DeBruijnBinder(pnames, ptypes, restpe) =>
3917
val isType = pnames.head.isTypeName
3918
val newParams = for (name <- pnames) yield
3919
if (isType) owner.newTypeParameter(name.toTypeName)
3920
else owner.newValueParameter(name.toTermName)
3921
paramStack = newParams :: paramStack
3923
foreach2(newParams, ptypes)((p, t) => p setInfo this(t))
3924
val restpe1 = this(restpe)
3925
if (isType) PolyType(newParams, restpe1)
3926
else MethodType(newParams, restpe1)
3927
} finally paramStack = paramStack.tail
3928
case DeBruijnIndex(level, idx, args) =>
3929
TypeRef(NoPrefix, paramStack(level)(idx), args map this)
3935
// Hash consing --------------------------------------------------------------
3937
private val initialUniquesCapacity = 4096
3938
private var uniques: util.WeakHashSet[Type] = _
3939
private var uniqueRunId = NoRunId
3941
protected def unique[T <: Type](tp: T): T = {
3942
if (Statistics.canEnable) Statistics.incCounter(rawTypeCount)
3943
if (uniqueRunId != currentRunId) {
3944
uniques = util.WeakHashSet[Type](initialUniquesCapacity)
3945
perRunCaches.recordCache(uniques)
3946
uniqueRunId = currentRunId
3948
(uniques findEntryOrUpdate tp).asInstanceOf[T]
3951
// Helper Classes ---------------------------------------------------------
3953
/** @PP: Unable to see why these apparently constant types should need vals
3954
* in every TypeConstraint, I lifted them out.
3956
private lazy val numericLoBound = IntClass.tpe
3957
private lazy val numericHiBound = intersectionType(List(ByteClass.tpe, CharClass.tpe), ScalaPackageClass)
3959
/** A class expressing upper and lower bounds constraints of type variables,
3960
* as well as their instantiations.
3962
class TypeConstraint(lo0: List[Type], hi0: List[Type], numlo0: Type, numhi0: Type, avoidWidening0: Boolean = false) {
3963
def this(lo0: List[Type], hi0: List[Type]) = this(lo0, hi0, NoType, NoType)
3964
def this(bounds: TypeBounds) = this(List(bounds.lo), List(bounds.hi))
3965
def this() = this(List(), List())
3967
/* Syncnote: Type constraints are assumed to be used from only one
3968
* thread. They are not exposed in api.Types and are used only locally
3969
* in operations that are exposed from types. Hence, no syncing of any
3970
* variables should be ncessesary.
3973
/** Guard these lists against AnyClass and NothingClass appearing,
3974
* else loBounds.isEmpty will have different results for an empty
3975
* constraint and one with Nothing as a lower bound. [Actually
3976
* guarding addLoBound/addHiBound somehow broke raw types so it
3977
* only guards against being created with them.]
3979
private var lobounds = lo0 filterNot typeIsNothing
3980
private var hibounds = hi0 filterNot typeIsAny
3981
private var numlo = numlo0
3982
private var numhi = numhi0
3983
private var avoidWidening = avoidWidening0
3985
def loBounds: List[Type] = if (numlo == NoType) lobounds else numlo :: lobounds
3986
def hiBounds: List[Type] = if (numhi == NoType) hibounds else numhi :: hibounds
3987
def avoidWiden: Boolean = avoidWidening
3989
def addLoBound(tp: Type, isNumericBound: Boolean = false) {
3990
// For some reason which is still a bit fuzzy, we must let Nothing through as
3991
// a lower bound despite the fact that Nothing is always a lower bound. My current
3992
// supposition is that the side-effecting type constraint accumulation mechanism
3993
// depends on these subtype tests being performed to make forward progress when
3994
// there are mutally recursive type vars.
3995
// See pos/t6367 and pos/t6499 for the competing test cases.
3996
val mustConsider = tp.typeSymbol match {
3997
case NothingClass => true
3998
case _ => !(lobounds contains tp)
4001
if (isNumericBound && isNumericValueType(tp)) {
4002
if (numlo == NoType || isNumericSubType(numlo, tp))
4004
else if (!isNumericSubType(tp, numlo))
4005
numlo = numericLoBound
4007
else lobounds ::= tp
4011
def checkWidening(tp: Type) {
4012
if(tp.isStable) avoidWidening = true
4014
case HasTypeMember(_, _) => avoidWidening = true
4019
def addHiBound(tp: Type, isNumericBound: Boolean = false) {
4020
// My current test case only demonstrates the need to let Nothing through as
4021
// a lower bound, but I suspect the situation is symmetrical.
4022
val mustConsider = tp.typeSymbol match {
4023
case AnyClass => true
4024
case _ => !(hibounds contains tp)
4028
if (isNumericBound && isNumericValueType(tp)) {
4029
if (numhi == NoType || isNumericSubType(tp, numhi))
4031
else if (!isNumericSubType(numhi, tp))
4032
numhi = numericHiBound
4034
else hibounds ::= tp
4038
def isWithinBounds(tp: Type): Boolean =
4039
lobounds.forall(_ <:< tp) &&
4040
hibounds.forall(tp <:< _) &&
4041
(numlo == NoType || (numlo weak_<:< tp)) &&
4042
(numhi == NoType || (tp weak_<:< numhi))
4044
var inst: Type = NoType // @M reduce visibility?
4046
def instValid = (inst ne null) && (inst ne NoType)
4048
def cloneInternal = {
4049
val tc = new TypeConstraint(lobounds, hibounds, numlo, numhi, avoidWidening)
4054
override def toString = {
4056
val lo = loBounds filterNot typeIsNothing
4057
val hi = hiBounds filterNot typeIsAny
4058
val lostr = if (lo.isEmpty) Nil else List(lo.mkString(" >: (", ", ", ")"))
4059
val histr = if (hi.isEmpty) Nil else List(hi.mkString(" <: (", ", ", ")"))
4061
lostr ++ histr mkString ("[", " | ", "]")
4063
if (inst eq NoType) boundsStr
4064
else boundsStr + " _= " + inst.safeToString
4068
class TypeUnwrapper(poly: Boolean, existential: Boolean, annotated: Boolean, nullary: Boolean) extends (Type => Type) {
4069
def apply(tp: Type): Type = tp match {
4070
case AnnotatedType(_, underlying, _) if annotated => apply(underlying)
4071
case ExistentialType(_, underlying) if existential => apply(underlying)
4072
case PolyType(_, underlying) if poly => apply(underlying)
4073
case NullaryMethodType(underlying) if nullary => apply(underlying)
4077
class ClassUnwrapper(existential: Boolean) extends TypeUnwrapper(poly = true, existential, annotated = true, nullary = false) {
4078
override def apply(tp: Type) = super.apply(tp.normalize)
4081
object unwrapToClass extends ClassUnwrapper(existential = true) { }
4082
object unwrapToStableClass extends ClassUnwrapper(existential = false) { }
4083
object unwrapWrapperTypes extends TypeUnwrapper(true, true, true, true) { }
4085
trait AnnotationFilter extends TypeMap {
4086
def keepAnnotation(annot: AnnotationInfo): Boolean
4088
override def mapOver(annot: AnnotationInfo) =
4089
if (keepAnnotation(annot)) super.mapOver(annot)
4090
else UnmappableAnnotation
4093
trait KeepOnlyTypeConstraints extends AnnotationFilter {
4094
// filter keeps only type constraint annotations
4095
def keepAnnotation(annot: AnnotationInfo) = annot matches TypeConstraintClass
4098
trait VariantTypeMap extends TypeMap {
4099
private[this] var _variance = 1
4101
override def variance = _variance
4102
def variance_=(x: Int) = _variance = x
4104
override protected def noChangeToSymbols(origSyms: List[Symbol]) =
4105
//OPT inline from forall to save on #closures
4109
if (sym.isAliasType) variance = 0
4110
val result = this(sym.info)
4112
(result eq sym.info) && noChangeToSymbols(rest)
4117
override protected def mapOverArgs(args: List[Type], tparams: List[Symbol]): List[Type] =
4118
map2Conserve(args, tparams) { (arg, tparam) =>
4120
if (tparam.isContravariant) variance = -variance
4121
else if (!tparam.isCovariant) variance = 0
4122
val arg1 = this(arg)
4127
/** Map this function over given type */
4128
override def mapOver(tp: Type): Type = tp match {
4129
case MethodType(params, result) =>
4130
variance = -variance
4131
val params1 = mapOver(params)
4132
variance = -variance
4133
val result1 = this(result)
4134
if ((params1 eq params) && (result1 eq result)) tp
4135
else copyMethodType(tp, params1, result1.substSym(params, params1))
4136
case PolyType(tparams, result) =>
4137
variance = -variance
4138
val tparams1 = mapOver(tparams)
4139
variance = -variance
4140
var result1 = this(result)
4141
if ((tparams1 eq tparams) && (result1 eq result)) tp
4142
else PolyType(tparams1, result1.substSym(tparams, tparams1))
4143
case TypeBounds(lo, hi) =>
4144
variance = -variance
4146
variance = -variance
4148
if ((lo1 eq lo) && (hi1 eq hi)) tp
4149
else TypeBounds(lo1, hi1)
4150
case tr @ TypeRef(pre, sym, args) =>
4151
val pre1 = this(pre)
4155
else if (variance == 0) // fast & safe path: don't need to look at typeparams
4156
args mapConserve this
4158
val tparams = sym.typeParams
4159
if (tparams.isEmpty) args
4160
else mapOverArgs(args, tparams)
4162
if ((pre1 eq pre) && (args1 eq args)) tp
4163
else copyTypeRef(tp, pre1, tr.coevolveSym(pre1), args1)
4169
// todo. move these into scala.reflect.api
4171
/** A prototype for mapping a function over all possible types
4173
abstract class TypeMap extends (Type => Type) {
4174
def apply(tp: Type): Type
4176
/** Mix in VariantTypeMap if you want variances to be significant.
4180
/** Map this function over given type */
4181
def mapOver(tp: Type): Type = tp match {
4182
case tr @ TypeRef(pre, sym, args) =>
4183
val pre1 = this(pre)
4184
val args1 = args mapConserve this
4185
if ((pre1 eq pre) && (args1 eq args)) tp
4186
else copyTypeRef(tp, pre1, tr.coevolveSym(pre1), args1)
4187
case ThisType(_) => tp
4188
case SingleType(pre, sym) =>
4189
if (sym.isPackageClass) tp // short path
4191
val pre1 = this(pre)
4193
else singleType(pre1, sym)
4195
case MethodType(params, result) =>
4196
val params1 = mapOver(params)
4197
val result1 = this(result)
4198
if ((params1 eq params) && (result1 eq result)) tp
4199
else copyMethodType(tp, params1, result1.substSym(params, params1))
4200
case PolyType(tparams, result) =>
4201
val tparams1 = mapOver(tparams)
4202
var result1 = this(result)
4203
if ((tparams1 eq tparams) && (result1 eq result)) tp
4204
else PolyType(tparams1, result1.substSym(tparams, tparams1))
4205
case NullaryMethodType(result) =>
4206
val result1 = this(result)
4207
if (result1 eq result) tp
4208
else NullaryMethodType(result1)
4209
case ConstantType(_) => tp
4210
case SuperType(thistp, supertp) =>
4211
val thistp1 = this(thistp)
4212
val supertp1 = this(supertp)
4213
if ((thistp1 eq thistp) && (supertp1 eq supertp)) tp
4214
else SuperType(thistp1, supertp1)
4215
case TypeBounds(lo, hi) =>
4218
if ((lo1 eq lo) && (hi1 eq hi)) tp
4219
else TypeBounds(lo1, hi1)
4220
case BoundedWildcardType(bounds) =>
4221
val bounds1 = this(bounds)
4222
if (bounds1 eq bounds) tp
4223
else BoundedWildcardType(bounds1.asInstanceOf[TypeBounds])
4224
case rtp @ RefinedType(parents, decls) =>
4225
val parents1 = parents mapConserve this
4226
val decls1 = mapOver(decls)
4227
//if ((parents1 eq parents) && (decls1 eq decls)) tp
4228
//else refinementOfClass(tp.typeSymbol, parents1, decls1)
4229
copyRefinedType(rtp, parents1, decls1)
4230
case ExistentialType(tparams, result) =>
4231
val tparams1 = mapOver(tparams)
4232
var result1 = this(result)
4233
if ((tparams1 eq tparams) && (result1 eq result)) tp
4234
else newExistentialType(tparams1, result1.substSym(tparams, tparams1))
4235
case OverloadedType(pre, alts) =>
4236
val pre1 = if (pre.isInstanceOf[ClassInfoType]) pre else this(pre)
4238
else OverloadedType(pre1, alts)
4239
case AntiPolyType(pre, args) =>
4240
val pre1 = this(pre)
4241
val args1 = args mapConserve (this)
4242
if ((pre1 eq pre) && (args1 eq args)) tp
4243
else AntiPolyType(pre1, args1)
4244
case tv@TypeVar(_, constr) =>
4245
if (constr.instValid) this(constr.inst)
4246
else tv.applyArgs(mapOverArgs(tv.typeArgs, tv.params)) //@M !args.isEmpty implies !typeParams.isEmpty
4247
case NotNullType(tp) =>
4250
else NotNullType(tp1)
4251
case AnnotatedType(annots, atp, selfsym) =>
4252
val annots1 = mapOverAnnotations(annots)
4253
val atp1 = this(atp)
4254
if ((annots1 eq annots) && (atp1 eq atp)) tp
4255
else if (annots1.isEmpty) atp1
4256
else AnnotatedType(annots1, atp1, selfsym)
4257
case DeBruijnIndex(shift, idx, args) =>
4258
val args1 = args mapConserve this
4259
if (args1 eq args) tp
4260
else DeBruijnIndex(shift, idx, args1)
4262
case ErrorType => tp
4263
case WildcardType => tp
4266
case ErasedSingleType(sym) => tp
4270
// throw new Error("mapOver inapplicable for " + tp);
4273
protected def mapOverArgs(args: List[Type], tparams: List[Symbol]): List[Type] =
4274
args mapConserve this
4276
/** Called by mapOver to determine whether the original symbols can
4277
* be returned, or whether they must be cloned. Overridden in VariantTypeMap.
4279
protected def noChangeToSymbols(origSyms: List[Symbol]) =
4280
origSyms forall (sym => sym.info eq this(sym.info))
4282
/** Map this function over given scope */
4283
def mapOver(scope: Scope): Scope = {
4284
val elems = scope.toList
4285
val elems1 = mapOver(elems)
4286
if (elems1 eq elems) scope
4287
else newScopeWith(elems1: _*)
4290
/** Map this function over given list of symbols */
4291
def mapOver(origSyms: List[Symbol]): List[Symbol] = {
4292
// fast path in case nothing changes due to map
4293
if (noChangeToSymbols(origSyms)) origSyms
4294
// map is not the identity --> do cloning properly
4295
else cloneSymbolsAndModify(origSyms, TypeMap.this)
4298
def mapOver(annot: AnnotationInfo): AnnotationInfo = {
4299
val AnnotationInfo(atp, args, assocs) = annot
4300
val atp1 = mapOver(atp)
4301
val args1 = mapOverAnnotArgs(args)
4302
// there is no need to rewrite assocs, as they are constants
4304
if ((args eq args1) && (atp eq atp1)) annot
4305
else if (args1.isEmpty && args.nonEmpty) UnmappableAnnotation // some annotation arg was unmappable
4306
else AnnotationInfo(atp1, args1, assocs) setPos annot.pos
4309
def mapOverAnnotations(annots: List[AnnotationInfo]): List[AnnotationInfo] = {
4310
val annots1 = annots mapConserve mapOver
4311
if (annots1 eq annots) annots
4312
else annots1 filterNot (_ eq UnmappableAnnotation)
4315
/** Map over a set of annotation arguments. If any
4316
* of the arguments cannot be mapped, then return Nil. */
4317
def mapOverAnnotArgs(args: List[Tree]): List[Tree] = {
4318
val args1 = args mapConserve mapOver
4319
if (args1 contains UnmappableTree) Nil
4323
def mapOver(tree: Tree): Tree =
4324
mapOver(tree, () => return UnmappableTree)
4326
/** Map a tree that is part of an annotation argument.
4327
* If the tree cannot be mapped, then invoke giveup().
4328
* The default is to transform the tree with
4329
* TypeMapTransformer.
4331
def mapOver(tree: Tree, giveup: ()=>Nothing): Tree =
4332
(new TypeMapTransformer).transform(tree)
4334
/** This transformer leaves the tree alone except to remap
4336
class TypeMapTransformer extends Transformer {
4337
override def transform(tree: Tree) = {
4338
val tree1 = super.transform(tree)
4339
val tpe1 = TypeMap.this(tree1.tpe)
4340
if ((tree eq tree1) && (tree.tpe eq tpe1))
4343
tree1.shallowDuplicate.setType(tpe1)
4348
abstract class TypeTraverser extends TypeMap {
4349
def traverse(tp: Type): Unit
4350
def apply(tp: Type): Type = { traverse(tp); tp }
4353
abstract class TypeTraverserWithResult[T] extends TypeTraverser {
4358
abstract class TypeCollector[T](initial: T) extends TypeTraverser {
4360
def collect(tp: Type) = {
4367
/** A collector that tests for existential types appearing at given variance in a type
4368
* @PP: Commenting out due to not being used anywhere.
4370
// class ContainsVariantExistentialCollector(v: Int) extends TypeCollector(false) with VariantTypeMap {
4373
// def traverse(tp: Type) = tp match {
4374
// case ExistentialType(_, _) if (variance == v) => result = true
4375
// case _ => mapOver(tp)
4379
// val containsCovariantExistentialCollector = new ContainsVariantExistentialCollector(1)
4380
// val containsContravariantExistentialCollector = new ContainsVariantExistentialCollector(-1)
4382
def typeParamsToExistentials(clazz: Symbol, tparams: List[Symbol]): List[Symbol] = {
4383
val eparams = mapWithIndex(tparams)((tparam, i) =>
4384
clazz.newExistential(newTypeName("?"+i), clazz.pos) setInfo tparam.info.bounds)
4386
eparams map (_ substInfo (tparams, eparams))
4388
def typeParamsToExistentials(clazz: Symbol): List[Symbol] =
4389
typeParamsToExistentials(clazz, clazz.typeParams)
4391
// note: it's important to write the two tests in this order,
4392
// as only typeParams forces the classfile to be read. See #400
4393
private def isRawIfWithoutArgs(sym: Symbol) =
4394
sym.isClass && sym.typeParams.nonEmpty && sym.isJavaDefined
4396
def isRaw(sym: Symbol, args: List[Type]) =
4397
!phase.erasedTypes && isRawIfWithoutArgs(sym) && args.isEmpty
4399
/** Is type tp a ''raw type''? */
4400
def isRawType(tp: Type) = tp match {
4401
case TypeRef(_, sym, args) => isRaw(sym, args)
4405
/** The raw to existential map converts a ''raw type'' to an existential type.
4406
* It is necessary because we might have read a raw type of a
4407
* parameterized Java class from a class file. At the time we read the type
4408
* the corresponding class file might still not be read, so we do not
4409
* know what the type parameters of the type are. Therefore
4410
* the conversion of raw types to existential types might not have taken place
4411
* in ClassFileparser.sigToType (where it is usually done).
4413
def rawToExistential = new TypeMap {
4414
private var expanded = immutable.Set[Symbol]()
4415
def apply(tp: Type): Type = tp match {
4416
case TypeRef(pre, sym, List()) if isRawIfWithoutArgs(sym) =>
4417
if (expanded contains sym) AnyRefClass.tpe
4420
val eparams = mapOver(typeParamsToExistentials(sym))
4421
existentialAbstraction(eparams, typeRef(apply(pre), sym, eparams map (_.tpe)))
4430
/** Used by existentialAbstraction.
4432
class ExistentialExtrapolation(tparams: List[Symbol]) extends VariantTypeMap {
4433
private val occurCount = mutable.HashMap[Symbol, Int]()
4434
private def countOccs(tp: Type) = {
4436
case TypeRef(_, sym, _) =>
4437
if (tparams contains sym)
4438
occurCount(sym) += 1
4442
def extrapolate(tpe: Type): Type = {
4443
tparams foreach (t => occurCount(t) = 0)
4445
for (tparam <- tparams)
4446
countOccs(tparam.info)
4451
def apply(tp: Type): Type = {
4452
val tp1 = mapOver(tp)
4453
if (variance == 0) tp1
4455
case TypeRef(pre, sym, args) if tparams contains sym =>
4456
val repl = if (variance == 1) dropSingletonType(tp1.bounds.hi) else tp1.bounds.lo
4457
//println("eliminate "+sym+"/"+repl+"/"+occurCount(sym)+"/"+(tparams exists (repl.contains)))//DEBUG
4458
if (!repl.typeSymbol.isBottomClass && occurCount(sym) == 1 && !(tparams exists (repl.contains)))
4465
override def mapOver(tp: Type): Type = tp match {
4466
case SingleType(pre, sym) =>
4467
if (sym.isPackageClass) tp // short path
4469
val pre1 = this(pre)
4470
if ((pre1 eq pre) || !pre1.isStable) tp
4471
else singleType(pre1, sym)
4473
case _ => super.mapOver(tp)
4476
// Do not discard the types of existential ident's. The
4477
// symbol of the Ident itself cannot be listed in the
4478
// existential's parameters, so the resulting existential
4479
// type would be ill-formed.
4480
override def mapOver(tree: Tree) = tree match {
4481
case Ident(_) if tree.tpe.isStable => tree
4482
case _ => super.mapOver(tree)
4486
def singletonBounds(hi: Type) = TypeBounds.upper(intersectionType(List(hi, SingletonClass.tpe)))
4488
/** Might the given symbol be important when calculating the prefix
4489
* of a type? When tp.asSeenFrom(pre, clazz) is called on `tp`,
4490
* the result will be `tp` unchanged if `pre` is trivial and `clazz`
4491
* is a symbol such that isPossiblePrefix(clazz) == false.
4493
def isPossiblePrefix(clazz: Symbol) = clazz.isClass && !clazz.isPackageClass
4495
private def skipPrefixOf(pre: Type, clazz: Symbol) = (
4496
(pre eq NoType) || (pre eq NoPrefix) || !isPossiblePrefix(clazz)
4499
/** A map to compute the asSeenFrom method */
4500
class AsSeenFromMap(pre: Type, clazz: Symbol) extends TypeMap with KeepOnlyTypeConstraints {
4501
var capturedSkolems: List[Symbol] = List()
4502
var capturedParams: List[Symbol] = List()
4504
override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
4505
object annotationArgRewriter extends TypeMapTransformer {
4506
private def canRewriteThis(sym: Symbol) = (
4507
(sym isNonBottomSubClass clazz)
4508
&& (pre.widen.typeSymbol isNonBottomSubClass sym)
4509
&& (pre.isStable || giveup())
4511
// what symbol should really be used?
4512
private def newTermSym() = {
4513
val p = pre.typeSymbol
4514
p.owner.newValue(p.name.toTermName, p.pos) setInfo pre
4516
/** Rewrite `This` trees in annotation argument trees */
4517
override def transform(tree: Tree): Tree = super.transform(tree) match {
4518
case This(_) if canRewriteThis(tree.symbol) => gen.mkAttributedQualifier(pre, newTermSym())
4522
annotationArgRewriter.transform(tree)
4525
def stabilize(pre: Type, clazz: Symbol): Type = {
4526
capturedParams find (_.owner == clazz) match {
4527
case Some(qvar) => qvar.tpe
4529
val qvar = clazz freshExistential nme.SINGLETON_SUFFIX setInfo singletonBounds(pre)
4530
capturedParams ::= qvar
4535
def apply(tp: Type): Type =
4537
case ThisType(sym) =>
4538
def toPrefix(pre: Type, clazz: Symbol): Type =
4539
if (skipPrefixOf(pre, clazz)) tp
4540
else if ((sym isNonBottomSubClass clazz) &&
4541
(pre.widen.typeSymbol isNonBottomSubClass sym)) {
4542
val pre1 = pre match {
4543
case SuperType(thistp, _) => thistp
4546
if (!(pre1.isStable ||
4547
pre1.typeSymbol.isPackageClass ||
4548
pre1.typeSymbol.isModuleClass && pre1.typeSymbol.isStatic)) {
4549
stabilize(pre1, sym)
4554
toPrefix(pre.baseType(clazz).prefix, clazz.owner)
4556
toPrefix(pre, clazz)
4557
case SingleType(pre, sym) =>
4558
if (sym.isPackageClass) tp // short path
4560
val pre1 = this(pre)
4562
else if (pre1.isStable) singleType(pre1, sym)
4563
else pre1.memberType(sym).resultType //todo: this should be rolled into existential abstraction
4565
// AM: Martin, is this description accurate?
4566
// walk the owner chain of `clazz` (the original argument to asSeenFrom) until we find the type param's owner (while rewriting pre as we crawl up the owner chain)
4567
// once we're at the owner, extract the information that pre encodes about the type param,
4568
// by minimally subsuming pre to the type instance of the class that owns the type param,
4569
// the type we're looking for is the type instance's type argument at the position corresponding to the type parameter
4570
// optimisation: skip this type parameter if it's not owned by a class, as those params are not influenced by the prefix through which they are seen
4571
// (concretely: 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)
4572
// (skolems also aren't affected: they are ruled out by the isTypeParameter check)
4573
case TypeRef(prefix, sym, args) if (sym.isTypeParameter && sym.owner.isClass) =>
4574
def toInstance(pre: Type, clazz: Symbol): Type =
4575
if (skipPrefixOf(pre, clazz)) mapOver(tp)
4576
//@M! see test pos/tcpoly_return_overriding.scala why mapOver is necessary
4578
def throwError = abort("" + tp + sym.locationString + " cannot be instantiated from " + pre.widen)
4580
val symclazz = sym.owner
4581
if (symclazz == clazz && !pre.widen.isInstanceOf[TypeVar] && (pre.widen.typeSymbol isNonBottomSubClass symclazz)) {
4582
// have to deconst because it may be a Class[T].
4583
pre.baseType(symclazz).deconst match {
4584
case TypeRef(_, basesym, baseargs) =>
4586
def instParam(ps: List[Symbol], as: List[Type]): Type =
4588
if (forInteractive) {
4589
val saved = settings.uniqid.value
4591
settings.uniqid.value = true
4592
println("*** stale type parameter: " + tp + sym.locationString + " cannot be instantiated from " + pre.widen)
4593
println("*** confused with params: " + sym + " in " + sym.owner + " not in " + ps + " of " + basesym)
4594
println("*** stacktrace = ")
4595
new Error().printStackTrace()
4596
} finally settings.uniqid.value = saved
4597
instParamRelaxed(basesym.typeParams, baseargs)
4599
} else if (sym eq ps.head)
4600
// @M! don't just replace the whole thing, might be followed by type application
4601
appliedType(as.head, args mapConserve (this)) // @M: was as.head
4602
else instParam(ps.tail, as.tail)
4604
/** Relaxed version of instParams which matches on names not symbols.
4605
* This is a last fallback in interactive mode because races in calls
4606
* from the IDE to the compiler may in rare cases lead to symbols referring
4607
* to type parameters that are no longer current.
4609
def instParamRelaxed(ps: List[Symbol], as: List[Type]): Type =
4610
if (ps.isEmpty) throwError
4611
else if (sym.name == ps.head.name)
4612
// @M! don't just replace the whole thing, might be followed by type application
4613
appliedType(as.head, args mapConserve (this)) // @M: was as.head
4614
else instParamRelaxed(ps.tail, as.tail)
4616
//Console.println("instantiating " + sym + " from " + basesym + " with " + basesym.typeParams + " and " + baseargs+", pre = "+pre+", symclazz = "+symclazz);//DEBUG
4617
if (sameLength(basesym.typeParams, baseargs))
4618
instParam(basesym.typeParams, baseargs)
4620
if (symclazz.tpe.parents exists typeIsErroneous)
4621
ErrorType // don't be to overzealous with throwing exceptions, see #2641
4624
"something is wrong (wrong class file?): "+basesym+
4625
" with type parameters "+
4626
basesym.typeParams.map(_.name).mkString("[",",","]")+
4627
" gets applied to arguments "+baseargs.mkString("[",",","]")+", phase = "+phase)
4628
case ExistentialType(tparams, qtpe) =>
4629
capturedSkolems = capturedSkolems union tparams
4630
toInstance(qtpe, clazz)
4634
} else toInstance(pre.baseType(clazz).prefix, clazz.owner)
4636
toInstance(pre, clazz)
4642
/** A base class to compute all substitutions */
4643
abstract class SubstMap[T](from: List[Symbol], to: List[T]) extends TypeMap {
4644
assert(sameLength(from, to), "Unsound substitution from "+ from +" to "+ to)
4646
/** Are `sym` and `sym1` the same? Can be tuned by subclasses. */
4647
protected def matches(sym: Symbol, sym1: Symbol): Boolean = sym eq sym1
4649
/** Map target to type, can be tuned by subclasses */
4650
protected def toType(fromtp: Type, tp: T): Type
4652
protected def renameBoundSyms(tp: Type): Type = tp match {
4653
case MethodType(ps, restp) =>
4654
createFromClonedSymbols(ps, restp)((ps1, tp1) => copyMethodType(tp, ps1, renameBoundSyms(tp1)))
4655
case PolyType(bs, restp) =>
4656
createFromClonedSymbols(bs, restp)((ps1, tp1) => PolyType(ps1, renameBoundSyms(tp1)))
4657
case ExistentialType(bs, restp) =>
4658
createFromClonedSymbols(bs, restp)(newExistentialType)
4663
def apply(tp0: Type): Type = if (from.isEmpty) tp0 else {
4664
@tailrec def subst(tp: Type, sym: Symbol, from: List[Symbol], to: List[T]): Type =
4665
if (from.isEmpty) tp
4666
// else if (to.isEmpty) error("Unexpected substitution on '%s': from = %s but to == Nil".format(tp, from))
4667
else if (matches(from.head, sym)) toType(tp, to.head)
4668
else subst(tp, sym, from.tail, to.tail)
4670
val boundSyms = tp0.boundSyms
4671
val tp1 = if (boundSyms.nonEmpty && (boundSyms exists from.contains)) renameBoundSyms(tp0) else tp0
4672
val tp = mapOver(tp1)
4676
// 1) arguments must also be substituted (even when the "head" of the
4677
// applied type has already been substituted)
4678
// example: (subst RBound[RT] from [type RT,type RBound] to
4679
// [type RT&,type RBound&]) = RBound&[RT&]
4680
// 2) avoid loops (which occur because alpha-conversion is
4681
// not performed properly imo)
4682
// e.g. if in class Iterable[a] there is a new Iterable[(a,b)],
4683
// we must replace the a in Iterable[a] by (a,b)
4684
// (must not recurse --> loops)
4685
// 3) replacing m by List in m[Int] should yield List[Int], not just List
4686
case TypeRef(NoPrefix, sym, args) =>
4687
appliedType(subst(tp, sym, from, to), args) // if args.isEmpty, appliedType is the identity
4688
case SingleType(NoPrefix, sym) =>
4689
subst(tp, sym, from, to)
4696
/** A map to implement the `substSym` method. */
4697
class SubstSymMap(from: List[Symbol], to: List[Symbol]) extends SubstMap(from, to) {
4698
def this(pairs: (Symbol, Symbol)*) = this(pairs.toList.map(_._1), pairs.toList.map(_._2))
4700
protected def toType(fromtp: Type, sym: Symbol) = fromtp match {
4701
case TypeRef(pre, _, args) => copyTypeRef(fromtp, pre, sym, args)
4702
case SingleType(pre, _) => singleType(pre, sym)
4704
override def apply(tp: Type): Type = if (from.isEmpty) tp else {
4705
@tailrec def subst(sym: Symbol, from: List[Symbol], to: List[Symbol]): Symbol =
4706
if (from.isEmpty) sym
4707
// else if (to.isEmpty) error("Unexpected substitution on '%s': from = %s but to == Nil".format(sym, from))
4708
else if (matches(from.head, sym)) to.head
4709
else subst(sym, from.tail, to.tail)
4711
case TypeRef(pre, sym, args) if pre ne NoPrefix =>
4712
val newSym = subst(sym, from, to)
4713
// mapOver takes care of subst'ing in args
4714
mapOver ( if (sym eq newSym) tp else copyTypeRef(tp, pre, newSym, args) )
4715
// assert(newSym.typeParams.length == sym.typeParams.length, "typars mismatch in SubstSymMap: "+(sym, sym.typeParams, newSym, newSym.typeParams))
4716
case SingleType(pre, sym) if pre ne NoPrefix =>
4717
val newSym = subst(sym, from, to)
4718
mapOver( if (sym eq newSym) tp else singleType(pre, newSym) )
4724
object mapTreeSymbols extends TypeMapTransformer {
4725
val strictCopy = newStrictTreeCopier
4727
def termMapsTo(sym: Symbol) = from indexOf sym match {
4729
case idx => Some(to(idx))
4732
// if tree.symbol is mapped to another symbol, passes the new symbol into the
4733
// constructor `trans` and sets the symbol and the type on the resulting tree.
4734
def transformIfMapped(tree: Tree)(trans: Symbol => Tree) = termMapsTo(tree.symbol) match {
4735
case Some(toSym) => trans(toSym) setSymbol toSym setType tree.tpe
4739
// changes trees which refer to one of the mapped symbols. trees are copied before attributes are modified.
4740
override def transform(tree: Tree) = {
4741
// super.transform maps symbol references in the types of `tree`. it also copies trees where necessary.
4742
super.transform(tree) match {
4743
case id @ Ident(_) =>
4744
transformIfMapped(id)(toSym =>
4745
strictCopy.Ident(id, toSym.name))
4747
case sel @ Select(qual, name) =>
4748
transformIfMapped(sel)(toSym =>
4749
strictCopy.Select(sel, qual, toSym.name))
4755
override def mapOver(tree: Tree, giveup: ()=>Nothing): Tree = {
4756
mapTreeSymbols.transform(tree)
4760
/** A map to implement the `subst` method. */
4761
class SubstTypeMap(from: List[Symbol], to: List[Type])
4762
extends SubstMap(from, to) {
4763
protected def toType(fromtp: Type, tp: Type) = tp
4765
override def mapOver(tree: Tree, giveup: () => Nothing): Tree = {
4766
object trans extends TypeMapTransformer {
4767
override def transform(tree: Tree) = tree match {
4769
from indexOf tree.symbol match {
4770
case -1 => super.transform(tree)
4773
if (totpe.isStable) tree.duplicate setType totpe
4777
super.transform(tree)
4780
trans.transform(tree)
4784
/** A map to implement the `substThis` method. */
4785
class SubstThisMap(from: Symbol, to: Type) extends TypeMap {
4786
def apply(tp: Type): Type = tp match {
4787
case ThisType(sym) if (sym == from) => to
4788
case _ => mapOver(tp)
4792
class SubstWildcardMap(from: List[Symbol]) extends TypeMap {
4793
def apply(tp: Type): Type = try {
4795
case TypeRef(_, sym, _) if from contains sym =>
4796
BoundedWildcardType(sym.info.bounds)
4801
case ex: MalformedType =>
4806
// dependent method types
4807
object IsDependentCollector extends TypeCollector(false) {
4808
def traverse(tp: Type) {
4809
if (tp.isImmediatelyDependent) result = true
4810
else if (!result) mapOver(tp.dealias)
4814
object ApproximateDependentMap extends TypeMap {
4815
def apply(tp: Type): Type =
4816
if (tp.isImmediatelyDependent) WildcardType
4820
/** Note: This map is needed even for non-dependent method types, despite what the name might imply.
4822
class InstantiateDependentMap(params: List[Symbol], actuals0: List[Type]) extends TypeMap with KeepOnlyTypeConstraints {
4823
private val actuals = actuals0.toIndexedSeq
4824
private val existentials = new Array[Symbol](actuals.size)
4825
def existentialsNeeded: List[Symbol] = existentials.iterator.filter(_ ne null).toList
4827
private object StableArgTp {
4828
// type of actual arg corresponding to param -- if the type is stable
4829
def unapply(param: Symbol): Option[Type] = (params indexOf param) match {
4832
val tp = actuals(pid)
4833
if (tp.isStable && (tp.typeSymbol != NothingClass)) Some(tp)
4838
/** Return the type symbol for referencing a parameter that's instantiated to an unstable actual argument.
4840
* To soundly abstract over an unstable value (x: T) while retaining the most type information,
4841
* use `x.type forSome { type x.type <: T with Singleton}`
4842
* `typeOf[T].narrowExistentially(symbolOf[x])`.
4844
* See also: captureThis in AsSeenFromMap.
4846
private def existentialFor(pid: Int) = {
4847
if (existentials(pid) eq null) {
4848
val param = params(pid)
4849
existentials(pid) = (
4850
param.owner.newExistential(param.name.toTypeName append nme.SINGLETON_SUFFIX, param.pos, param.flags)
4851
setInfo singletonBounds(actuals(pid))
4857
private object UnstableArgTp {
4858
// existential quantifier and type of corresponding actual arg with unstable type
4859
def unapply(param: Symbol): Option[(Symbol, Type)] = (params indexOf param) match {
4862
val sym = existentialFor(pid)
4863
Some((sym, sym.tpe)) // refers to an actual value, must be kind-*
4867
private object StabilizedArgTp {
4868
def unapply(param: Symbol): Option[Type] =
4870
case StableArgTp(tp) => Some(tp) // (1)
4871
case UnstableArgTp(_, tp) => Some(tp) // (2)
4876
/** instantiate `param.type` to the (sound approximation of the) type `T`
4877
* of the actual argument `arg` that was passed in for `param`
4879
* (1) If `T` is stable, we can just use that.
4881
* (2) SI-3873: it'd be unsound to instantiate `param.type` to an unstable `T`,
4882
* so we approximate to `X forSome {type X <: T with Singleton}` -- we can't soundly say more.
4884
def apply(tp: Type): Type = tp match {
4885
case SingleType(NoPrefix, StabilizedArgTp(tp)) => tp
4886
case _ => mapOver(tp)
4889
//AM propagate more info to annotations -- this seems a bit ad-hoc... (based on code by spoon)
4890
override def mapOver(arg: Tree, giveup: ()=>Nothing): Tree = {
4891
// TODO: this should be simplified; in the stable case, one can
4892
// probably just use an Ident to the tree.symbol.
4894
// @PP: That leads to failure here, where stuff no longer has type
4895
// 'String @Annot("stuff")' but 'String @Annot(x)'.
4897
// def m(x: String): String @Annot(x) = x
4898
// val stuff = m("stuff")
4900
// (TODO cont.) Why an existential in the non-stable case?
4902
// @PP: In the following:
4904
// def m = { val x = "three" ; val y: String @Annot(x) = x; y }
4906
// m is typed as 'String @Annot(x) forSome { val x: String }'.
4908
// Both examples are from run/constrained-types.scala.
4909
object treeTrans extends Transformer {
4910
override def transform(tree: Tree): Tree = tree.symbol match {
4911
case StableArgTp(tp) => gen.mkAttributedQualifier(tp, tree.symbol)
4912
case UnstableArgTp(quant, tp) => Ident(quant) copyAttrs tree setType tp
4913
case _ => super.transform(tree)
4916
treeTrans transform arg
4920
object StripAnnotationsMap extends TypeMap {
4921
def apply(tp: Type): Type = tp match {
4922
case AnnotatedType(_, atp, _) =>
4929
/** A map to convert every occurrence of a wildcard type to a fresh
4931
object wildcardToTypeVarMap extends TypeMap {
4932
def apply(tp: Type): Type = tp match {
4933
case WildcardType =>
4934
TypeVar(tp, new TypeConstraint)
4935
case BoundedWildcardType(bounds) =>
4936
TypeVar(tp, new TypeConstraint(bounds))
4942
/** A map to convert every occurrence of a type variable to a wildcard type. */
4943
object typeVarToOriginMap extends TypeMap {
4944
def apply(tp: Type): Type = tp match {
4945
case TypeVar(origin, _) => origin
4946
case _ => mapOver(tp)
4950
/** A map to implement the `contains` method. */
4951
class ContainsCollector(sym: Symbol) extends TypeCollector(false) {
4952
def traverse(tp: Type) {
4954
tp.normalize match {
4955
case TypeRef(_, sym1, _) if (sym == sym1) => result = true
4956
case SingleType(_, sym1) if (sym == sym1) => result = true
4957
case _ => mapOver(tp)
4962
override def mapOver(arg: Tree) = {
4965
if (t.symbol == sym)
4972
/** A map to implement the `contains` method. */
4973
class ContainsTypeCollector(t: Type) extends TypeCollector(false) {
4974
def traverse(tp: Type) {
4976
if (tp eq t) result = true
4980
override def mapOver(arg: Tree) = {
4988
/** A map to implement the `filter` method. */
4989
class FilterTypeCollector(p: Type => Boolean) extends TypeCollector[List[Type]](Nil) {
4990
def withFilter(q: Type => Boolean) = new FilterTypeCollector(tp => p(tp) && q(tp))
4992
override def collect(tp: Type) = super.collect(tp).reverse
4994
def traverse(tp: Type) {
4995
if (p(tp)) result ::= tp
5000
/** A map to implement the `collect` method. */
5001
class CollectTypeCollector[T](pf: PartialFunction[Type, T]) extends TypeCollector[List[T]](Nil) {
5002
override def collect(tp: Type) = super.collect(tp).reverse
5004
def traverse(tp: Type) {
5005
if (pf.isDefinedAt(tp)) result ::= pf(tp)
5010
class ForEachTypeTraverser(f: Type => Unit) extends TypeTraverser {
5011
def traverse(tp: Type) {
5017
/** A map to implement the `filter` method. */
5018
class FindTypeCollector(p: Type => Boolean) extends TypeCollector[Option[Type]](None) {
5019
def traverse(tp: Type) {
5020
if (result.isEmpty) {
5021
if (p(tp)) result = Some(tp)
5027
/** A map to implement the `contains` method. */
5028
object ErroneousCollector extends TypeCollector(false) {
5029
def traverse(tp: Type) {
5038
* A more persistent version of `Type#memberType` which does not require
5039
* that the symbol is a direct member of the prefix.
5047
* object S1 extends F[T]
5049
* class S2 extends F[T]
5051
* object O extends C[Int] {
5052
* def foo(f: F[Int]) = f match {...} // need to enumerate sealed subtypes of the scrutinee here.
5054
* class S3 extends O.F[String]
5056
* nestedMemberType(<S1>, <O.type>, <C>) = O.X.S1.type
5057
* nestedMemberType(<S2>, <O.type>, <C>) = O.S2.type
5058
* nestedMemberType(<S3>, <O.type>, <C>) = S3.type
5061
* @param sym The symbol of the subtype
5062
* @param pre The prefix from which the symbol is seen
5065
def nestedMemberType(sym: Symbol, pre: Type, owner: Symbol): Type = {
5066
def loop(tp: Type): Type =
5067
if (tp.isTrivial) tp
5068
else if (tp.prefix.typeSymbol isNonBottomSubClass owner) {
5069
val widened = tp match {
5070
case _: ConstantType => tp // Java enum constants: don't widen to the enum type!
5071
case _ => tp.widen // C.X.type widens to C.this.X.type, otherwise `tp asSeenFrom (pre, C)` has no effect.
5073
val memType = widened asSeenFrom (pre, tp.typeSymbol.owner)
5074
if (tp eq widened) memType else memType.narrow
5076
else loop(tp.prefix) memberType tp.typeSymbol
5078
val result = loop(sym.tpeHK)
5079
assert(sym.isTerm || result.typeSymbol == sym, s"($result).typeSymbol = ${result.typeSymbol}; expected ${sym}")
5083
/** The most deeply nested owner that contains all the symbols
5084
* of thistype or prefixless typerefs/singletype occurrences in given type.
5086
private def commonOwner(t: Type): Symbol = commonOwner(t :: Nil)
5088
/** The most deeply nested owner that contains all the symbols
5089
* of thistype or prefixless typerefs/singletype occurrences in given list
5092
private def commonOwner(tps: List[Type]): Symbol = {
5093
if (tps.isEmpty) NoSymbol
5095
commonOwnerMap.clear()
5096
tps foreach (commonOwnerMap traverse _)
5097
if (commonOwnerMap.result ne null) commonOwnerMap.result else NoSymbol
5101
protected def commonOwnerMap: CommonOwnerMap = commonOwnerMapObj
5103
protected class CommonOwnerMap extends TypeTraverserWithResult[Symbol] {
5104
var result: Symbol = _
5106
def clear() { result = null }
5108
private def register(sym: Symbol) {
5109
// First considered type is the trivial result.
5110
if ((result eq null) || (sym eq NoSymbol))
5113
while ((result ne NoSymbol) && (result ne sym) && !(sym isNestedIn result))
5114
result = result.owner
5116
def traverse(tp: Type) = tp.normalize match {
5117
case ThisType(sym) => register(sym)
5118
case TypeRef(NoPrefix, sym, args) => register(sym.owner) ; args foreach traverse
5119
case SingleType(NoPrefix, sym) => register(sym.owner)
5120
case _ => mapOver(tp)
5124
private lazy val commonOwnerMapObj = new CommonOwnerMap
5126
class MissingAliasControl extends ControlThrowable
5127
val missingAliasException = new MissingAliasControl
5128
class MissingTypeControl extends ControlThrowable
5130
object adaptToNewRunMap extends TypeMap {
5132
private def adaptToNewRun(pre: Type, sym: Symbol): Symbol = {
5133
if (phase.flatClasses || sym.isRootSymbol || (pre eq NoPrefix) || (pre eq NoType) || sym.isPackageClass)
5135
else if (sym.isModuleClass) {
5136
val sourceModule1 = adaptToNewRun(pre, sym.sourceModule)
5138
sourceModule1.moduleClass orElse sourceModule1.initialize.moduleClass orElse {
5139
val msg = "Cannot adapt module class; sym = %s, sourceModule = %s, sourceModule.moduleClass = %s => sourceModule1 = %s, sourceModule1.moduleClass = %s"
5140
debuglog(msg.format(sym, sym.sourceModule, sym.sourceModule.moduleClass, sourceModule1, sourceModule1.moduleClass))
5145
var rebind0 = pre.findMember(sym.name, BRIDGE, 0, true) orElse {
5146
if (sym.isAliasType) throw missingAliasException
5147
debugwarn(pre+"."+sym+" does no longer exist, phase = "+phase)
5148
throw new MissingTypeControl // For build manager and presentation compiler purposes
5150
/** The two symbols have the same fully qualified name */
5151
def corresponds(sym1: Symbol, sym2: Symbol): Boolean =
5152
sym1.name == sym2.name && (sym1.isPackageClass || corresponds(sym1.owner, sym2.owner))
5153
if (!corresponds(sym.owner, rebind0.owner)) {
5154
debuglog("ADAPT1 pre = "+pre+", sym = "+sym.fullLocationString+", rebind = "+rebind0.fullLocationString)
5155
val bcs = pre.baseClasses.dropWhile(bc => !corresponds(bc, sym.owner));
5157
assert(pre.typeSymbol.isRefinementClass, pre) // if pre is a refinementclass it might be a structural type => OK to leave it in.
5159
rebind0 = pre.baseType(bcs.head).member(sym.name)
5161
"ADAPT2 pre = " + pre +
5162
", bcs.head = " + bcs.head +
5163
", sym = " + sym.fullLocationString +
5164
", rebind = " + rebind0.fullLocationString
5167
rebind0.suchThat(sym => sym.isType || sym.isStable) orElse {
5168
debuglog("" + phase + " " +phase.flatClasses+sym.owner+sym.name+" "+sym.isType)
5169
throw new MalformedType(pre, sym.nameString)
5173
def apply(tp: Type): Type = tp match {
5174
case ThisType(sym) =>
5176
val sym1 = adaptToNewRun(sym.owner.thisType, sym)
5177
if (sym1 == sym) tp else ThisType(sym1)
5179
case ex: MissingTypeControl =>
5182
case SingleType(pre, sym) =>
5183
if (sym.isPackage) tp
5185
val pre1 = this(pre)
5187
val sym1 = adaptToNewRun(pre1, sym)
5188
if ((pre1 eq pre) && (sym1 eq sym)) tp
5189
else singleType(pre1, sym1)
5191
case _: MissingTypeControl =>
5195
case TypeRef(pre, sym, args) =>
5196
if (sym.isPackageClass) tp
5198
val pre1 = this(pre)
5199
val args1 = args mapConserve (this)
5201
val sym1 = adaptToNewRun(pre1, sym)
5202
if ((pre1 eq pre) && (sym1 eq sym) && (args1 eq args)/* && sym.isExternal*/) {
5204
} else if (sym1 == NoSymbol) {
5205
debugwarn("adapt fail: "+pre+" "+pre1+" "+sym)
5208
copyTypeRef(tp, pre1, sym1, args1)
5211
case ex: MissingAliasControl =>
5213
case _: MissingTypeControl =>
5217
case MethodType(params, restp) =>
5218
val restp1 = this(restp)
5219
if (restp1 eq restp) tp
5220
else copyMethodType(tp, params, restp1)
5221
case NullaryMethodType(restp) =>
5222
val restp1 = this(restp)
5223
if (restp1 eq restp) tp
5224
else NullaryMethodType(restp1)
5225
case PolyType(tparams, restp) =>
5226
val restp1 = this(restp)
5227
if (restp1 eq restp) tp
5228
else PolyType(tparams, restp1)
5230
// Lukas: we need to check (together) whether we should also include parameter types
5231
// of PolyType and MethodType in adaptToNewRun
5233
case ClassInfoType(parents, decls, clazz) =>
5234
if (clazz.isPackageClass) tp
5236
val parents1 = parents mapConserve (this)
5237
if (parents1 eq parents) tp
5238
else ClassInfoType(parents1, decls, clazz)
5240
case RefinedType(parents, decls) =>
5241
val parents1 = parents mapConserve (this)
5242
if (parents1 eq parents) tp
5243
else refinedType(parents1, tp.typeSymbol.owner, decls, tp.typeSymbol.owner.pos)
5244
case SuperType(_, _) => mapOver(tp)
5245
case TypeBounds(_, _) => mapOver(tp)
5246
case TypeVar(_, _) => mapOver(tp)
5247
case AnnotatedType(_,_,_) => mapOver(tp)
5248
case NotNullType(_) => mapOver(tp)
5249
case ExistentialType(_, _) => mapOver(tp)
5254
final case class SubTypePair(tp1: Type, tp2: Type) {
5255
// SI-8146 we used to implement equality here in terms of pairwise =:=.
5256
// But, this was inconsistent with hashCode, which was based on the
5257
// Type#hashCode, based on the structure of types, not the meaning.
5258
// Now, we use `Type#{equals,hashCode}` as the (consistent) basis for
5259
// detecting cycles (aka keeping subtyping decidable.)
5261
// I added tests to show that we detect the cycle: neg/t8146-no-finitary*
5263
override def toString = tp1+" <:<? "+tp2
5266
// Helper Methods -------------------------------------------------------------
5268
/** The maximum allowable depth of lubs or glbs over types `ts`.
5270
def lubDepth(ts: List[Type]): Int = {
5271
val td = typeDepth(ts)
5272
val bd = baseTypeSeqDepth(ts)
5273
lubDepthAdjust(td, td max bd)
5276
/** The maximum allowable depth of lubs or glbs over given types,
5277
* as a function over the maximum depth `td` of these types, and
5278
* the maximum depth `bd` of all types in the base type sequences of these types.
5280
private def lubDepthAdjust(td: Int, bd: Int): Int =
5281
if (settings.XfullLubs.value) bd
5282
else if (bd <= 3) bd
5283
else if (bd <= 5) td max (bd - 1)
5284
else if (bd <= 7) td max (bd - 2)
5285
else (td - 1) max (bd - 3)
5287
/** The maximum depth of type `tp` */
5288
def typeDepth(tp: Type): Int = tp match {
5289
case TypeRef(pre, sym, args) =>
5290
typeDepth(pre) max typeDepth(args) + 1
5291
case RefinedType(parents, decls) =>
5292
typeDepth(parents) max typeDepth(decls.toList.map(_.info)) + 1
5293
case TypeBounds(lo, hi) =>
5294
typeDepth(lo) max typeDepth(hi)
5295
case MethodType(paramtypes, result) =>
5297
case NullaryMethodType(result) =>
5299
case PolyType(tparams, result) =>
5300
typeDepth(result) max typeDepth(tparams map (_.info)) + 1
5301
case ExistentialType(tparams, result) =>
5302
typeDepth(result) max typeDepth(tparams map (_.info)) + 1
5307
private def maxDepth(tps: List[Type], by: Type => Int): Int = {
5308
//OPT replaced with tailrecursive function to save on #closures
5311
// for (tp <- tps) d = d max by(tp) //!!!OPT!!!
5313
def loop(tps: List[Type], acc: Int): Int = tps match {
5314
case tp :: rest => loop(rest, acc max by(tp))
5320
private def typeDepth(tps: List[Type]): Int = maxDepth(tps, typeDepth)
5321
private def baseTypeSeqDepth(tps: List[Type]): Int = maxDepth(tps, _.baseTypeSeqDepth)
5323
/** Is intersection of given types populated? That is,
5324
* for all types tp1, tp2 in intersection
5325
* for all common base classes bc of tp1 and tp2
5326
* let bt1, bt2 be the base types of tp1, tp2 relative to class bc
5328
* bt1 and bt2 have the same prefix, and
5329
* any corresponding non-variant type arguments of bt1 and bt2 are the same
5331
def isPopulated(tp1: Type, tp2: Type): Boolean = {
5332
def isConsistent(tp1: Type, tp2: Type): Boolean = (tp1, tp2) match {
5333
case (TypeRef(pre1, sym1, args1), TypeRef(pre2, sym2, args2)) =>
5334
assert(sym1 == sym2)
5336
forall3(args1, args2, sym1.typeParams) { (arg1, arg2, tparam) =>
5337
//if (tparam.variance == 0 && !(arg1 =:= arg2)) Console.println("inconsistent: "+arg1+"!="+arg2)//DEBUG
5338
if (tparam.variance == 0) arg1 =:= arg2
5339
else if (arg1.isInstanceOf[TypeVar])
5340
// if left-hand argument is a typevar, make it compatible with variance
5341
// this is for more precise pattern matching
5342
// todo: work this in the spec of this method
5343
// also: think what happens if there are embedded typevars?
5344
if (tparam.variance < 0) arg1 <:< arg2 else arg2 <:< arg1
5347
case (et: ExistentialType, _) =>
5348
et.withTypeVars(isConsistent(_, tp2))
5349
case (_, et: ExistentialType) =>
5350
et.withTypeVars(isConsistent(tp1, _))
5353
def check(tp1: Type, tp2: Type) =
5354
if (tp1.typeSymbol.isClass && tp1.typeSymbol.hasFlag(FINAL))
5355
tp1 <:< tp2 || isNumericValueClass(tp1.typeSymbol) && isNumericValueClass(tp2.typeSymbol)
5356
else tp1.baseClasses forall (bc =>
5357
tp2.baseTypeIndex(bc) < 0 || isConsistent(tp1.baseType(bc), tp2.baseType(bc)))
5359
check(tp1, tp2)/* && check(tp2, tp1)*/ // need to investgate why this can't be made symmetric -- neg/gadts1 fails, and run/existials also.
5362
/** Does a pattern of type `patType` need an outer test when executed against
5363
* selector type `selType` in context defined by `currentOwner`?
5365
def needsOuterTest(patType: Type, selType: Type, currentOwner: Symbol) = {
5366
def createDummyClone(pre: Type): Type = {
5367
val dummy = currentOwner.enclClass.newValue(nme.ANYname).setInfo(pre.widen)
5368
singleType(ThisType(currentOwner.enclClass), dummy)
5370
def maybeCreateDummyClone(pre: Type, sym: Symbol): Type = pre match {
5371
case SingleType(pre1, sym1) =>
5372
if (sym1.isModule && sym1.isStatic) {
5374
} else if (sym1.isModule && sym.owner == sym1.moduleClass) {
5375
val pre2 = maybeCreateDummyClone(pre1, sym1)
5376
if (pre2 eq NoType) pre2
5377
else singleType(pre2, sym1)
5379
createDummyClone(pre)
5381
case ThisType(clazz) =>
5382
if (clazz.isModuleClass)
5383
maybeCreateDummyClone(clazz.typeOfThis, sym)
5384
else if (sym.owner == clazz && (sym.hasFlag(PRIVATE) || sym.privateWithin == clazz))
5387
createDummyClone(pre)
5391
// See the test for SI-7214 for motivation for dealias. Later `treeCondStrategy#outerTest`
5392
// generates an outer test based on `patType.prefix` with automatically dealises.
5393
patType.dealias match {
5394
case TypeRef(pre, sym, args) =>
5395
val pre1 = maybeCreateDummyClone(pre, sym)
5396
(pre1 ne NoType) && isPopulated(copyTypeRef(patType, pre1, sym, args), selType)
5402
private var subsametypeRecursions: Int = 0
5404
private def isUnifiable(pre1: Type, pre2: Type) =
5405
(beginsWithTypeVarOrIsRefined(pre1) || beginsWithTypeVarOrIsRefined(pre2)) && (pre1 =:= pre2)
5407
/** Returns true iff we are past phase specialize,
5408
* sym1 and sym2 are two existential skolems with equal names and bounds,
5409
* and pre1 and pre2 are equal prefixes
5411
private def isSameSpecializedSkolem(sym1: Symbol, sym2: Symbol, pre1: Type, pre2: Type) = {
5412
sym1.isExistentialSkolem && sym2.isExistentialSkolem &&
5413
sym1.name == sym2.name &&
5414
phase.specialized &&
5415
sym1.info =:= sym2.info &&
5419
private def isSubPre(pre1: Type, pre2: Type, sym: Symbol) =
5420
if ((pre1 ne pre2) && (pre1 ne NoPrefix) && (pre2 ne NoPrefix) && pre1 <:< pre2) {
5421
if (settings.debug.value) println(s"new isSubPre $sym: $pre1 <:< $pre2")
5426
private def equalSymsAndPrefixes(sym1: Symbol, pre1: Type, sym2: Symbol, pre2: Type): Boolean =
5427
if (sym1 == sym2) sym1.hasPackageFlag || sym1.owner.hasPackageFlag || phase.erasedTypes || pre1 =:= pre2
5428
else (sym1.name == sym2.name) && isUnifiable(pre1, pre2)
5430
/** Do `tp1` and `tp2` denote equivalent types? */
5431
def isSameType(tp1: Type, tp2: Type): Boolean = try {
5432
if (Statistics.canEnable) Statistics.incCounter(sametypeCount)
5433
subsametypeRecursions += 1
5434
//OPT cutdown on Function0 allocation
5436
// undoLog undoUnless {
5437
// isSameType1(tp1, tp2)
5442
val before = undoLog.log
5446
isSameType1(tp1, tp2)
5447
} finally if (!result) undoLog.undoTo(before)
5449
} finally undoLog.unlock()
5451
subsametypeRecursions -= 1
5452
// XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866)
5453
// it doesn't help to keep separate recursion counts for the three methods that now share it
5454
// if (subsametypeRecursions == 0) undoLog.clear()
5457
def isDifferentType(tp1: Type, tp2: Type): Boolean = try {
5458
subsametypeRecursions += 1
5459
undoLog undo { // undo type constraints that arise from operations in this block
5460
!isSameType1(tp1, tp2)
5463
subsametypeRecursions -= 1
5464
// XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866)
5465
// it doesn't help to keep separate recursion counts for the three methods that now share it
5466
// if (subsametypeRecursions == 0) undoLog.clear()
5469
def isDifferentTypeConstructor(tp1: Type, tp2: Type): Boolean = tp1 match {
5470
case TypeRef(pre1, sym1, _) =>
5472
case TypeRef(pre2, sym2, _) => sym1 != sym2 || isDifferentType(pre1, pre2)
5478
def normalizePlus(tp: Type) =
5479
if (isRawType(tp)) rawToExistential(tp)
5484
def normalizePlus(tp: Type) = tp match {
5485
case TypeRef(pre, sym, List()) =>
5486
if (!sym.isInitialized) sym.rawInfo.load(sym)
5487
if (sym.isJavaDefined && !sym.typeParams.isEmpty) rawToExistential(tp)
5489
case _ => tp.normalize
5493
private def isSameType0(tp1: Type, tp2: Type): Boolean = {
5494
if (tp1 eq tp2) return true
5496
case (ErrorType, _) => true
5497
case (WildcardType, _) => true
5498
case (_, ErrorType) => true
5499
case (_, WildcardType) => true
5501
case (NoType, _) => false
5502
case (NoPrefix, _) => tp2.typeSymbol.isPackageClass
5503
case (_, NoType) => false
5504
case (_, NoPrefix) => tp1.typeSymbol.isPackageClass
5506
case (ThisType(sym1), ThisType(sym2))
5507
if (sym1 == sym2) =>
5509
case (SingleType(pre1, sym1), SingleType(pre2, sym2))
5510
if (equalSymsAndPrefixes(sym1, pre1, sym2, pre2)) =>
5513
case (SingleType(pre1, sym1), ThisType(sym2))
5514
if (sym1.isModule &&
5515
sym1.moduleClass == sym2 &&
5516
pre1 =:= sym2.owner.thisType) =>
5518
case (ThisType(sym1), SingleType(pre2, sym2))
5519
if (sym2.isModule &&
5520
sym2.moduleClass == sym1 &&
5521
pre2 =:= sym1.owner.thisType) =>
5524
case (ConstantType(value1), ConstantType(value2)) =>
5526
case (TypeRef(pre1, sym1, args1), TypeRef(pre2, sym2, args2)) =>
5527
equalSymsAndPrefixes(sym1, pre1, sym2, pre2) &&
5528
((tp1.isHigherKinded && tp2.isHigherKinded && tp1.normalize =:= tp2.normalize) ||
5529
isSameTypes(args1, args2))
5530
// @M! normalize reduces higher-kinded case to PolyType's
5531
case (RefinedType(parents1, ref1), RefinedType(parents2, ref2)) =>
5532
def isSubScope(s1: Scope, s2: Scope): Boolean = s2.toList.forall {
5534
var e1 = s1.lookupEntry(sym2.name)
5536
val substSym = sym2.info.substThis(sym2.owner, e1.sym.owner.thisType)
5538
while (!isEqual && (e1 ne null)) {
5539
isEqual = e1.sym.info =:= substSym
5540
e1 = s1.lookupNextEntry(e1)
5545
//Console.println("is same? " + tp1 + " " + tp2 + " " + tp1.typeSymbol.owner + " " + tp2.typeSymbol.owner)//DEBUG
5546
isSameTypes(parents1, parents2) && isSubScope(ref1, ref2) && isSubScope(ref2, ref1)
5547
case (MethodType(params1, res1), MethodType(params2, res2)) =>
5548
// new dependent types: probably fix this, use substSym as done for PolyType
5549
(isSameTypes(tp1.paramTypes, tp2.paramTypes) &&
5551
tp1.isImplicit == tp2.isImplicit)
5552
case (PolyType(tparams1, res1), PolyType(tparams2, res2)) =>
5553
// assert((tparams1 map (_.typeParams.length)) == (tparams2 map (_.typeParams.length)))
5554
(tparams1.length == tparams2.length) && (tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) && // @M looks like it might suffer from same problem as #2210
5555
res1 =:= res2.substSym(tparams2, tparams1)
5556
case (ExistentialType(tparams1, res1), ExistentialType(tparams2, res2)) =>
5557
(tparams1.length == tparams2.length) && (tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) && // @M looks like it might suffer from same problem as #2210
5558
res1 =:= res2.substSym(tparams2, tparams1)
5559
case (TypeBounds(lo1, hi1), TypeBounds(lo2, hi2)) =>
5560
lo1 =:= lo2 && hi1 =:= hi2
5561
case (BoundedWildcardType(bounds), _) =>
5562
bounds containsType tp2
5563
case (_, BoundedWildcardType(bounds)) =>
5564
bounds containsType tp1
5565
case (tv @ TypeVar(_,_), tp) =>
5566
tv.registerTypeEquality(tp, true)
5567
case (tp, tv @ TypeVar(_,_)) =>
5568
tv.registerTypeEquality(tp, false)
5569
case (AnnotatedType(_,_,_), _) =>
5570
annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations
5571
case (_, AnnotatedType(_,_,_)) =>
5572
annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations
5573
case (_: SingletonType, _: SingletonType) =>
5575
while (origin1.underlying.isInstanceOf[SingletonType]) {
5576
assert(origin1 ne origin1.underlying, origin1)
5577
origin1 = origin1.underlying
5580
while (origin2.underlying.isInstanceOf[SingletonType]) {
5581
assert(origin2 ne origin2.underlying, origin2)
5582
origin2 = origin2.underlying
5584
((origin1 ne tp1) || (origin2 ne tp2)) && (origin1 =:= origin2)
5588
val tp1n = normalizePlus(tp1)
5589
val tp2n = normalizePlus(tp2)
5590
((tp1n ne tp1) || (tp2n ne tp2)) && isSameType(tp1n, tp2n)
5594
private def isSameType1(tp1: Type, tp2: Type): Boolean = {
5596
(tp1 eq ErrorType) || (tp1 eq WildcardType) ||
5597
(tp2 eq ErrorType) || (tp2 eq WildcardType))
5599
else if ((tp1 eq NoType) || (tp2 eq NoType))
5601
else if (tp1 eq NoPrefix) // !! I do not see how this would be warranted by the spec
5602
tp2.typeSymbol.isPackageClass
5603
else if (tp2 eq NoPrefix) // !! I do not see how this would be warranted by the spec
5604
tp1.typeSymbol.isPackageClass
5606
isSameType2(tp1, tp2) || {
5607
val tp1n = normalizePlus(tp1)
5608
val tp2n = normalizePlus(tp2)
5609
((tp1n ne tp1) || (tp2n ne tp2)) && isSameType(tp1n, tp2n)
5614
def isSameType2(tp1: Type, tp2: Type): Boolean = {
5616
case tr1: TypeRef =>
5618
case tr2: TypeRef =>
5619
return (equalSymsAndPrefixes(tr1.sym, tr1.pre, tr2.sym, tr2.pre) &&
5620
((tp1.isHigherKinded && tp2.isHigherKinded && tp1.normalize =:= tp2.normalize) ||
5621
isSameTypes(tr1.args, tr2.args))) ||
5622
((tr1.pre, tr2.pre) match {
5623
case (tv @ TypeVar(_,_), _) => tv.registerTypeSelection(tr1.sym, tr2)
5624
case (_, tv @ TypeVar(_,_)) => tv.registerTypeSelection(tr2.sym, tr1)
5627
case _: SingleType =>
5628
return isSameType2(tp2, tp1) // put singleton type on the left, caught below
5631
case tt1: ThisType =>
5633
case tt2: ThisType =>
5634
if (tt1.sym == tt2.sym) return true
5637
case st1: SingleType =>
5639
case st2: SingleType =>
5640
if (equalSymsAndPrefixes(st1.sym, st1.pre, st2.sym, st2.pre)) return true
5641
case TypeRef(pre2, sym2, Nil) =>
5642
if (sym2.isModuleClass && equalSymsAndPrefixes(st1.sym, st1.pre, sym2.sourceModule, pre2)) return true
5645
case ct1: ConstantType =>
5647
case ct2: ConstantType =>
5648
return (ct1.value == ct2.value)
5651
case rt1: RefinedType =>
5653
case rt2: RefinedType => //
5654
def isSubScope(s1: Scope, s2: Scope): Boolean = s2.toList.forall {
5656
var e1 = s1.lookupEntry(sym2.name)
5658
val substSym = sym2.info.substThis(sym2.owner, e1.sym.owner)
5660
while (!isEqual && (e1 ne null)) {
5661
isEqual = e1.sym.info =:= substSym
5662
e1 = s1.lookupNextEntry(e1)
5667
//Console.println("is same? " + tp1 + " " + tp2 + " " + tp1.typeSymbol.owner + " " + tp2.typeSymbol.owner)//DEBUG
5668
return isSameTypes(rt1.parents, rt2.parents) && {
5669
val decls1 = rt1.decls
5670
val decls2 = rt2.decls
5671
isSubScope(decls1, decls2) && isSubScope(decls2, decls1)
5675
case mt1: MethodType =>
5677
case mt2: MethodType =>
5678
return isSameTypes(mt1.paramTypes, mt2.paramTypes) &&
5679
mt1.resultType =:= mt2.resultType.substSym(mt2.params, mt1.params) &&
5680
mt1.isImplicit == mt2.isImplicit
5681
// note: no case NullaryMethodType(restpe) => return mt1.params.isEmpty && mt1.resultType =:= restpe
5684
case NullaryMethodType(restpe1) =>
5686
// note: no case mt2: MethodType => return mt2.params.isEmpty && restpe =:= mt2.resultType
5687
case NullaryMethodType(restpe2) =>
5688
return restpe1 =:= restpe2
5691
case PolyType(tparams1, res1) =>
5693
case PolyType(tparams2, res2) =>
5694
// assert((tparams1 map (_.typeParams.length)) == (tparams2 map (_.typeParams.length)))
5695
// @M looks like it might suffer from same problem as #2210
5697
(sameLength(tparams1, tparams2)) && // corresponds does not check length of two sequences before checking the predicate
5698
(tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) &&
5699
res1 =:= res2.substSym(tparams2, tparams1)
5703
case ExistentialType(tparams1, res1) =>
5705
case ExistentialType(tparams2, res2) =>
5706
// @M looks like it might suffer from same problem as #2210
5708
// corresponds does not check length of two sequences before checking the predicate -- faster & needed to avoid crasher in #2956
5709
sameLength(tparams1, tparams2) &&
5710
(tparams1 corresponds tparams2)(_.info =:= _.info.substSym(tparams2, tparams1)) &&
5711
res1 =:= res2.substSym(tparams2, tparams1)
5715
case TypeBounds(lo1, hi1) =>
5717
case TypeBounds(lo2, hi2) =>
5718
return lo1 =:= lo2 && hi1 =:= hi2
5721
case BoundedWildcardType(bounds) =>
5722
return bounds containsType tp2
5726
case BoundedWildcardType(bounds) =>
5727
return bounds containsType tp1
5731
case tv @ TypeVar(_,_) =>
5732
return tv.registerTypeEquality(tp2, true)
5736
case tv @ TypeVar(_,_) =>
5737
return tv.registerTypeEquality(tp1, false)
5741
case _: AnnotatedType =>
5742
return annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations
5746
case _: AnnotatedType =>
5747
return annotationsConform(tp1, tp2) && annotationsConform(tp2, tp1) && tp1.withoutAnnotations =:= tp2.withoutAnnotations
5751
case _: SingletonType =>
5753
case _: SingletonType =>
5754
def chaseDealiasedUnderlying(tp: Type): Type = {
5756
var next = origin.underlying.dealias
5757
while (next.isInstanceOf[SingletonType]) {
5758
assert(origin ne next, origin)
5760
next = origin.underlying.dealias
5764
val origin1 = chaseDealiasedUnderlying(tp1)
5765
val origin2 = chaseDealiasedUnderlying(tp2)
5766
((origin1 ne tp1) || (origin2 ne tp2)) && (origin1 =:= origin2)
5775
/** Are `tps1` and `tps2` lists of pairwise equivalent types? */
5776
def isSameTypes(tps1: List[Type], tps2: List[Type]): Boolean = (tps1 corresponds tps2)(_ =:= _)
5778
/** True if two lists have the same length. Since calling length on linear sequences
5779
* is O(n), it is an inadvisable way to test length equality.
5781
final def sameLength(xs1: List[_], xs2: List[_]) = compareLengths(xs1, xs2) == 0
5782
@tailrec final def compareLengths(xs1: List[_], xs2: List[_]): Int =
5783
if (xs1.isEmpty) { if (xs2.isEmpty) 0 else -1 }
5784
else if (xs2.isEmpty) 1
5785
else compareLengths(xs1.tail, xs2.tail)
5787
/** Again avoiding calling length, but the lengthCompare interface is clunky.
5789
final def hasLength(xs: List[_], len: Int) = xs.lengthCompare(len) == 0
5791
private val pendingSubTypes = new mutable.HashSet[SubTypePair]
5792
private var basetypeRecursions: Int = 0
5793
private val pendingBaseTypes = new mutable.HashSet[Type]
5795
def isSubType(tp1: Type, tp2: Type): Boolean = isSubType(tp1, tp2, AnyDepth)
5797
def isSubType(tp1: Type, tp2: Type, depth: Int): Boolean = try {
5798
subsametypeRecursions += 1
5800
//OPT cutdown on Function0 allocation
5802
// undoLog undoUnless { // if subtype test fails, it should not affect constraints on typevars
5803
// if (subsametypeRecursions >= LogPendingSubTypesThreshold) {
5804
// val p = new SubTypePair(tp1, tp2)
5805
// if (pendingSubTypes(p))
5809
// pendingSubTypes += p
5810
// isSubType2(tp1, tp2, depth)
5812
// pendingSubTypes -= p
5815
// isSubType2(tp1, tp2, depth)
5821
val before = undoLog.log
5824
try result = { // if subtype test fails, it should not affect constraints on typevars
5825
if (subsametypeRecursions >= LogPendingSubTypesThreshold) {
5826
val p = new SubTypePair(tp1, tp2)
5827
if (pendingSubTypes(p))
5828
false // see neg/t8146-no-finitary*
5831
pendingSubTypes += p
5832
isSubType2(tp1, tp2, depth)
5834
pendingSubTypes -= p
5837
isSubType2(tp1, tp2, depth)
5839
} finally if (!result) undoLog.undoTo(before)
5842
} finally undoLog.unlock()
5844
subsametypeRecursions -= 1
5845
// XXX AM TODO: figure out when it is safe and needed to clear the log -- the commented approach below is too eager (it breaks #3281, #3866)
5846
// it doesn't help to keep separate recursion counts for the three methods that now share it
5847
// if (subsametypeRecursions == 0) undoLog.clear()
5850
/** Does this type have a prefix that begins with a type variable,
5851
* or is it a refinement type? For type prefixes that fulfil this condition,
5852
* type selections with the same name of equal (as determined by `=:=`) prefixes are
5853
* considered equal in regard to `=:=`.
5855
def beginsWithTypeVarOrIsRefined(tp: Type): Boolean = tp match {
5856
case SingleType(pre, sym) =>
5857
!(sym hasFlag PACKAGE) && beginsWithTypeVarOrIsRefined(pre)
5858
case tv@TypeVar(_, constr) =>
5859
!tv.instValid || beginsWithTypeVarOrIsRefined(constr.inst)
5860
case RefinedType(_, _) =>
5866
@deprecated("The compiler doesn't use this so you shouldn't either - it will be removed", "2.10.0")
5867
def instTypeVar(tp: Type): Type = tp match {
5868
case TypeRef(pre, sym, args) =>
5869
copyTypeRef(tp, instTypeVar(pre), sym, args)
5870
case SingleType(pre, sym) =>
5871
singleType(instTypeVar(pre), sym)
5872
case TypeVar(_, constr) =>
5873
instTypeVar(constr.inst)
5878
def isErrorOrWildcard(tp: Type) = (tp eq ErrorType) || (tp eq WildcardType)
5880
def isSingleType(tp: Type) = tp match {
5881
case ThisType(_) | SuperType(_, _) | SingleType(_, _) => true
5885
def isConstantType(tp: Type) = tp match {
5886
case ConstantType(_) => true
5890
/** This is defined and named as it is because the goal is to exclude source
5891
* level types which are not value types (e.g. MethodType) without excluding
5892
* necessary internal types such as WildcardType. There are also non-value
5893
* types which can be used as type arguments (e.g. type constructors.)
5895
def isUseableAsTypeArg(tp: Type) = (
5896
isInternalTypeUsedAsTypeArg(tp) // the subset of internal types which can be type args
5897
|| isHKTypeRef(tp) // not a value type, but ok as a type arg
5898
|| isValueElseNonValue(tp) // otherwise only value types
5901
private def isHKTypeRef(tp: Type) = tp match {
5902
case TypeRef(_, sym, Nil) => tp.isHigherKinded
5905
@tailrec final def isUseableAsTypeArgs(tps: List[Type]): Boolean = tps match {
5907
case x :: xs => isUseableAsTypeArg(x) && isUseableAsTypeArgs(xs)
5910
/** The "third way", types which are neither value types nor
5911
* non-value types as defined in the SLS, further divided into
5912
* types which are used internally in type applications and
5913
* types which are not.
5915
private def isInternalTypeNotUsedAsTypeArg(tp: Type): Boolean = tp match {
5916
case AntiPolyType(pre, targs) => true
5917
case ClassInfoType(parents, defs, clazz) => true
5918
case DeBruijnIndex(level, index, args) => true
5919
case ErasedValueType(tref) => true
5920
case NoPrefix => true
5922
case SuperType(thistpe, supertpe) => true
5923
case TypeBounds(lo, hi) => true
5926
private def isInternalTypeUsedAsTypeArg(tp: Type): Boolean = tp match {
5927
case WildcardType => true
5928
case BoundedWildcardType(_) => true
5929
case ErrorType => true
5930
case _: TypeVar => true
5933
private def isAlwaysValueType(tp: Type) = tp match {
5934
case RefinedType(_, _) => true
5935
case ExistentialType(_, _) => true
5936
case ConstantType(_) => true
5939
private def isAlwaysNonValueType(tp: Type) = tp match {
5940
case OverloadedType(_, _) => true
5941
case NullaryMethodType(_) => true
5942
case MethodType(_, _) => true
5943
case PolyType(_, MethodType(_, _)) => true
5946
/** Should be called only with types for which a clear true/false answer
5947
* can be given: true == value type, false == non-value type. Otherwise,
5948
* an exception is thrown.
5950
private def isValueElseNonValue(tp: Type): Boolean = tp match {
5951
case tp if isAlwaysValueType(tp) => true
5952
case tp if isAlwaysNonValueType(tp) => false
5953
case AnnotatedType(_, underlying, _) => isValueElseNonValue(underlying)
5954
case SingleType(_, sym) => sym.isValue // excludes packages and statics
5955
case TypeRef(_, _, _) if tp.isHigherKinded => false // excludes type constructors
5956
case ThisType(sym) => !sym.isPackageClass // excludes packages
5957
case TypeRef(_, sym, _) => !sym.isPackageClass // excludes packages
5958
case PolyType(_, _) => true // poly-methods excluded earlier
5959
case tp => sys.error("isValueElseNonValue called with third-way type " + tp)
5962
/** SLS 3.2, Value Types
5963
* Is the given type definitely a value type? A true result means
5964
* it verifiably is, but a false result does not mean it is not,
5965
* only that it cannot be assured. To avoid false positives, this
5966
* defaults to false, but since Type is not sealed, one should take
5967
* a false answer with a grain of salt. This method may be primarily
5968
* useful as documentation; it is likely that !isNonValueType(tp)
5969
* will serve better than isValueType(tp).
5971
def isValueType(tp: Type) = isValueElseNonValue(tp)
5973
/** SLS 3.3, Non-Value Types
5974
* Is the given type definitely a non-value type, as defined in SLS 3.3?
5975
* The specification-enumerated non-value types are method types, polymorphic
5976
* method types, and type constructors. Supplements to the specified set of
5977
* non-value types include: types which wrap non-value symbols (packages
5978
* abd statics), overloaded types. Varargs and by-name types T* and (=>T) are
5979
* not designated non-value types because there is code which depends on using
5980
* them as type arguments, but their precise status is unclear.
5982
def isNonValueType(tp: Type) = !isValueElseNonValue(tp)
5984
def isNonRefinementClassType(tpe: Type) = tpe match {
5985
case SingleType(_, sym) => sym.isModuleClass
5986
case TypeRef(_, sym, _) => sym.isClass && !sym.isRefinementClass
5987
case ErrorType => true
5991
// @assume tp1.isHigherKinded || tp2.isHigherKinded
5992
def isHKSubType0(tp1: Type, tp2: Type, depth: Int): Boolean = (
5993
tp1.typeSymbol == NothingClass
5995
tp2.typeSymbol == AnyClass // @M Any and Nothing are super-type resp. subtype of every well-kinded type
5996
|| // @M! normalize reduces higher-kinded case to PolyType's
5997
((tp1.normalize.withoutAnnotations , tp2.normalize.withoutAnnotations) match {
5998
case (PolyType(tparams1, res1), PolyType(tparams2, res2)) => // @assume tp1.isHigherKinded && tp2.isHigherKinded (as they were both normalized to PolyType)
5999
sameLength(tparams1, tparams2) && {
6000
if (tparams1.head.owner.isMethod) { // fast-path: polymorphic method type -- type params cannot be captured
6001
(tparams1 corresponds tparams2)((p1, p2) => p2.info.substSym(tparams2, tparams1) <:< p1.info) &&
6002
res1 <:< res2.substSym(tparams2, tparams1)
6003
} else { // normalized higher-kinded type
6004
//@M for an example of why we need to generate fresh symbols, see neg/tcpoly_ticket2101.scala
6005
val tpsFresh = cloneSymbols(tparams1)
6007
(tparams1 corresponds tparams2)((p1, p2) =>
6008
p2.info.substSym(tparams2, tpsFresh) <:< p1.info.substSym(tparams1, tpsFresh)) &&
6009
res1.substSym(tparams1, tpsFresh) <:< res2.substSym(tparams2, tpsFresh)
6011
//@M the forall in the previous test could be optimised to the following,
6012
// but not worth the extra complexity since it only shaves 1s from quick.comp
6013
// (List.forall2(tpsFresh/*optimisation*/, tparams2)((p1, p2) =>
6014
// p2.info.substSym(tparams2, tpsFresh) <:< p1.info /*optimisation, == (p1 from tparams1).info.substSym(tparams1, tpsFresh)*/) &&
6015
// this optimisation holds because inlining cloneSymbols in `val tpsFresh = cloneSymbols(tparams1)` gives:
6016
// val tpsFresh = tparams1 map (_.cloneSymbol)
6017
// for (tpFresh <- tpsFresh) tpFresh.setInfo(tpFresh.info.substSym(tparams1, tpsFresh))
6019
} && annotationsConform(tp1.normalize, tp2.normalize)
6020
case (_, _) => false // @assume !tp1.isHigherKinded || !tp2.isHigherKinded
6021
// --> thus, cannot be subtypes (Any/Nothing has already been checked)
6024
def isSubArgs(tps1: List[Type], tps2: List[Type], tparams: List[Symbol], depth: Int): Boolean = {
6025
def isSubArg(t1: Type, t2: Type, variance: Int) =
6026
(variance > 0 || isSubType(t2, t1, depth)) &&
6027
(variance < 0 || isSubType(t1, t2, depth))
6028
corresponds3(tps1, tps2, tparams map (_.variance))(isSubArg)
6031
def differentOrNone(tp1: Type, tp2: Type) = if (tp1 eq tp2) NoType else tp1
6033
/** Does type `tp1` conform to `tp2`? */
6034
private def isSubType2(tp1: Type, tp2: Type, depth: Int): Boolean = {
6035
if ((tp1 eq tp2) || isErrorOrWildcard(tp1) || isErrorOrWildcard(tp2)) return true
6036
if ((tp1 eq NoType) || (tp2 eq NoType)) return false
6037
if (tp1 eq NoPrefix) return (tp2 eq NoPrefix) || tp2.typeSymbol.isPackageClass // !! I do not see how the "isPackageClass" would be warranted by the spec
6038
if (tp2 eq NoPrefix) return tp1.typeSymbol.isPackageClass
6039
if (isSingleType(tp1) && isSingleType(tp2) || isConstantType(tp1) && isConstantType(tp2)) return tp1 =:= tp2
6040
if (tp1.isHigherKinded || tp2.isHigherKinded) return isHKSubType0(tp1, tp2, depth)
6042
/** First try, on the right:
6043
* - unwrap Annotated types, BoundedWildcardTypes,
6044
* - bind TypeVars on the right, if lhs is not Annotated nor BoundedWildcard
6045
* - handle common cases for first-kind TypeRefs on both sides as a fast path.
6047
def firstTry = tp2 match {
6048
// fast path: two typerefs, none of them HK
6049
case tr2: TypeRef =>
6051
case tr1: TypeRef =>
6056
(((if (sym1 == sym2) phase.erasedTypes || sym1.owner.hasPackageFlag || isSubType(pre1, pre2, depth)
6057
else (sym1.name == sym2.name && !sym1.isModuleClass && !sym2.isModuleClass &&
6058
(isUnifiable(pre1, pre2) ||
6059
isSameSpecializedSkolem(sym1, sym2, pre1, pre2) ||
6060
sym2.isAbstractType && isSubPre(pre1, pre2, sym2)))) &&
6061
isSubArgs(tr1.args, tr2.args, sym1.typeParams, depth))
6064
val base = tr1 baseType sym2
6065
(base ne tr1) && isSubType(base, tr2, depth)
6068
thirdTryRef(tr1, tr2))
6072
case AnnotatedType(_, _, _) =>
6073
isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) &&
6074
annotationsConform(tp1, tp2)
6075
case BoundedWildcardType(bounds) =>
6076
isSubType(tp1, bounds.hi, depth)
6077
case tv2 @ TypeVar(_, constr2) =>
6079
case AnnotatedType(_, _, _) | BoundedWildcardType(_) =>
6082
tv2.registerBound(tp1, true)
6088
/** Second try, on the left:
6089
* - unwrap AnnotatedTypes, BoundedWildcardTypes,
6091
* - handle existential types by skolemization.
6093
def secondTry = tp1 match {
6094
case AnnotatedType(_, _, _) =>
6095
isSubType(tp1.withoutAnnotations, tp2.withoutAnnotations, depth) &&
6096
annotationsConform(tp1, tp2)
6097
case BoundedWildcardType(bounds) =>
6098
isSubType(tp1.bounds.lo, tp2, depth)
6099
case tv @ TypeVar(_,_) =>
6100
tv.registerBound(tp2, false)
6101
case ExistentialType(_, _) =>
6103
skolemizationLevel += 1
6104
isSubType(tp1.skolemizeExistential, tp2, depth)
6106
skolemizationLevel -= 1
6112
def thirdTryRef(tp1: Type, tp2: TypeRef): Boolean = {
6115
case NotNullClass => tp1.isNotNull
6116
case SingletonClass => tp1.isStable || fourthTry
6117
case _: ClassSymbol =>
6118
if (isRaw(sym2, tp2.args))
6119
isSubType(tp1, rawToExistential(tp2), depth)
6120
else if (sym2.name == tpnme.REFINE_CLASS_NAME)
6121
isSubType(tp1, sym2.info, depth)
6124
case _: TypeSymbol =>
6125
if (sym2 hasFlag DEFERRED) {
6126
val tp2a = tp2.bounds.lo
6127
isDifferentTypeConstructor(tp2, tp2a) &&
6128
isSubType(tp1, tp2a, depth) ||
6131
isSubType(tp1.normalize, tp2.normalize, depth)
6138
/** Third try, on the right:
6139
* - decompose refined types.
6140
* - handle typerefs, existentials, and notnull types.
6141
* - handle left+right method types, polytypes, typebounds
6143
def thirdTry = tp2 match {
6144
case tr2: TypeRef =>
6145
thirdTryRef(tp1, tr2)
6146
case rt2: RefinedType =>
6147
(rt2.parents forall (isSubType(tp1, _, depth))) &&
6148
(rt2.decls forall (specializesSym(tp1, _, depth)))
6149
case et2: ExistentialType =>
6150
et2.withTypeVars(isSubType(tp1, _, depth), depth) || fourthTry
6151
case nn2: NotNullType =>
6152
tp1.isNotNull && isSubType(tp1, nn2.underlying, depth)
6153
case mt2: MethodType =>
6155
case mt1 @ MethodType(params1, res1) =>
6156
val params2 = mt2.params
6157
val res2 = mt2.resultType
6158
(sameLength(params1, params2) &&
6159
mt1.isImplicit == mt2.isImplicit &&
6160
matchingParams(params1, params2, mt1.isJava, mt2.isJava) &&
6161
isSubType(res1.substSym(params1, params2), res2, depth))
6162
// TODO: if mt1.params.isEmpty, consider NullaryMethodType?
6166
case pt2 @ NullaryMethodType(_) =>
6168
// TODO: consider MethodType mt for which mt.params.isEmpty??
6169
case pt1 @ NullaryMethodType(_) =>
6170
isSubType(pt1.resultType, pt2.resultType, depth)
6174
case TypeBounds(lo2, hi2) =>
6176
case TypeBounds(lo1, hi1) =>
6177
isSubType(lo2, lo1, depth) && isSubType(hi1, hi2, depth)
6185
/** Fourth try, on the left:
6186
* - handle typerefs, refined types, notnull and singleton types.
6188
def fourthTry = tp1 match {
6189
case tr1 @ TypeRef(pre1, sym1, _) =>
6191
case NothingClass => true
6194
case TypeRef(_, sym2, _) =>
6197
isSingleType(tp2) && isSubType(tp1, tp2.widen, depth)
6199
case _: ClassSymbol =>
6200
if (isRaw(sym1, tr1.args))
6201
isSubType(rawToExistential(tp1), tp2, depth)
6202
else if (sym1.isModuleClass) tp2 match {
6203
case SingleType(pre2, sym2) => equalSymsAndPrefixes(sym1.sourceModule, pre1, sym2, pre2)
6206
else if (sym1.isRefinementClass)
6207
isSubType(sym1.info, tp2, depth)
6210
case _: TypeSymbol =>
6211
if (sym1 hasFlag DEFERRED) {
6212
val tp1a = tp1.bounds.hi
6213
isDifferentTypeConstructor(tp1, tp1a) && isSubType(tp1a, tp2, depth)
6215
isSubType(tp1.normalize, tp2.normalize, depth)
6220
case RefinedType(parents1, _) =>
6221
parents1 exists (isSubType(_, tp2, depth))
6222
case _: SingletonType | _: NotNullType =>
6223
isSubType(tp1.underlying, tp2, depth)
6231
private def containsNull(sym: Symbol): Boolean =
6232
sym.isClass && sym != NothingClass &&
6233
!(sym isNonBottomSubClass AnyValClass) &&
6234
!(sym isNonBottomSubClass NotNullClass)
6236
/** Are `tps1` and `tps2` lists of equal length such that all elements
6237
* of `tps1` conform to corresponding elements of `tps2`?
6239
def isSubTypes(tps1: List[Type], tps2: List[Type]): Boolean = (tps1 corresponds tps2)(_ <:< _)
6241
/** Does type `tp` implement symbol `sym` with same or
6242
* stronger type? Exact only if `sym` is a member of some
6243
* refinement type, otherwise we might return false negatives.
6245
def specializesSym(tp: Type, sym: Symbol): Boolean =
6246
specializesSym(tp, sym, AnyDepth)
6248
def specializesSym(tp: Type, sym: Symbol, depth: Int): Boolean =
6249
tp.typeSymbol == NothingClass ||
6250
tp.typeSymbol == NullClass && containsNull(sym.owner) || {
6251
def specializedBy(membr: Symbol): Boolean =
6252
membr == sym || specializesSym(tp.narrow, membr, sym.owner.thisType, sym, depth)
6253
val member = tp.nonPrivateMember(sym.name)
6254
if (member eq NoSymbol) false
6255
else if (member.isOverloaded) member.alternatives exists specializedBy
6256
else specializedBy(member)
6258
// (tp.nonPrivateMember(sym.name).alternatives exists
6259
// (alt => sym == alt || specializesSym(tp.narrow, alt, sym.owner.thisType, sym, depth)))
6262
/** Does member `sym1` of `tp1` have a stronger type
6263
* than member `sym2` of `tp2`?
6265
private def specializesSym(tp1: Type, sym1: Symbol, tp2: Type, sym2: Symbol, depth: Int): Boolean = {
6266
val info1 = tp1.memberInfo(sym1)
6267
val info2 = tp2.memberInfo(sym2).substThis(tp2.typeSymbol, tp1)
6268
//System.out.println("specializes "+tp1+"."+sym1+":"+info1+sym1.locationString+" AND "+tp2+"."+sym2+":"+info2)//DEBUG
6269
( sym2.isTerm && isSubType(info1, info2, depth) && (!sym2.isStable || sym1.isStable)
6270
|| sym2.isAbstractType && {
6271
val memberTp1 = tp1.memberType(sym1)
6272
// println("kinds conform? "+(memberTp1, tp1, sym2, kindsConform(List(sym2), List(memberTp1), tp2, sym2.owner)))
6273
info2.bounds.containsType(memberTp1) &&
6274
kindsConform(List(sym2), List(memberTp1), tp1, sym1.owner)
6276
|| sym2.isAliasType && tp2.memberType(sym2).substThis(tp2.typeSymbol, tp1) =:= tp1.memberType(sym1) //@MAT ok
6280
/** A function implementing `tp1` matches `tp2`. */
6281
final def matchesType(tp1: Type, tp2: Type, alwaysMatchSimple: Boolean): Boolean = {
6282
def matchesQuantified(tparams1: List[Symbol], tparams2: List[Symbol], res1: Type, res2: Type): Boolean = (
6283
sameLength(tparams1, tparams2) &&
6284
matchesType(res1, res2.substSym(tparams2, tparams1), alwaysMatchSimple)
6288
case ExistentialType(_, res2) if alwaysMatchSimple =>
6289
matchesType(tp1, res2, true)
6290
case MethodType(_, _) =>
6292
case PolyType(_, _) =>
6295
alwaysMatchSimple || tp1 =:= tp2
6298
case mt1 @ MethodType(params1, res1) =>
6300
case mt2 @ MethodType(params2, res2) =>
6301
// sameLength(params1, params2) was used directly as pre-screening optimization (now done by matchesQuantified -- is that ok, performancewise?)
6302
mt1.isImplicit == mt2.isImplicit &&
6303
matchingParams(params1, params2, mt1.isJava, mt2.isJava) &&
6304
matchesQuantified(params1, params2, res1, res2)
6305
case NullaryMethodType(res2) =>
6306
if (params1.isEmpty) matchesType(res1, res2, alwaysMatchSimple)
6307
else matchesType(tp1, res2, alwaysMatchSimple)
6308
case ExistentialType(_, res2) =>
6309
alwaysMatchSimple && matchesType(tp1, res2, true)
6310
case TypeRef(_, sym, Nil) =>
6311
params1.isEmpty && sym.isModuleClass && matchesType(res1, tp2, alwaysMatchSimple)
6315
case mt1 @ NullaryMethodType(res1) =>
6317
case mt2 @ MethodType(Nil, res2) => // could never match if params nonEmpty, and !mt2.isImplicit is implied by empty param list
6318
matchesType(res1, res2, alwaysMatchSimple)
6319
case NullaryMethodType(res2) =>
6320
matchesType(res1, res2, alwaysMatchSimple)
6321
case ExistentialType(_, res2) =>
6322
alwaysMatchSimple && matchesType(tp1, res2, true)
6323
case TypeRef(_, sym, Nil) if sym.isModuleClass =>
6324
matchesType(res1, tp2, alwaysMatchSimple)
6326
matchesType(res1, tp2, alwaysMatchSimple)
6328
case PolyType(tparams1, res1) =>
6330
case PolyType(tparams2, res2) =>
6331
if ((tparams1 corresponds tparams2)(_ eq _))
6332
matchesType(res1, res2, alwaysMatchSimple)
6334
matchesQuantified(tparams1, tparams2, res1, res2)
6335
case ExistentialType(_, res2) =>
6336
alwaysMatchSimple && matchesType(tp1, res2, true)
6338
false // remember that tparams1.nonEmpty is now an invariant of PolyType
6340
case ExistentialType(tparams1, res1) =>
6342
case ExistentialType(tparams2, res2) =>
6343
matchesQuantified(tparams1, tparams2, res1, res2)
6345
if (alwaysMatchSimple) matchesType(res1, tp2, true)
6348
case TypeRef(_, sym, Nil) if sym.isModuleClass =>
6350
case MethodType(Nil, res2) => matchesType(tp1, res2, alwaysMatchSimple)
6351
case NullaryMethodType(res2) => matchesType(tp1, res2, alwaysMatchSimple)
6359
/** matchesType above is an optimized version of the following implementation:
6361
def matchesType2(tp1: Type, tp2: Type, alwaysMatchSimple: Boolean): Boolean = {
6362
def matchesQuantified(tparams1: List[Symbol], tparams2: List[Symbol], res1: Type, res2: Type): Boolean =
6363
tparams1.length == tparams2.length &&
6364
matchesType(res1, res2.substSym(tparams2, tparams1), alwaysMatchSimple)
6366
case (MethodType(params1, res1), MethodType(params2, res2)) =>
6367
params1.length == params2.length && // useful pre-secreening optimization
6368
matchingParams(params1, params2, tp1.isInstanceOf[JavaMethodType], tp2.isInstanceOf[JavaMethodType]) &&
6369
matchesType(res1, res2, alwaysMatchSimple) &&
6370
tp1.isImplicit == tp2.isImplicit
6371
case (PolyType(tparams1, res1), PolyType(tparams2, res2)) =>
6372
matchesQuantified(tparams1, tparams2, res1, res2)
6373
case (NullaryMethodType(rtp1), MethodType(List(), rtp2)) =>
6374
matchesType(rtp1, rtp2, alwaysMatchSimple)
6375
case (MethodType(List(), rtp1), NullaryMethodType(rtp2)) =>
6376
matchesType(rtp1, rtp2, alwaysMatchSimple)
6377
case (ExistentialType(tparams1, res1), ExistentialType(tparams2, res2)) =>
6378
matchesQuantified(tparams1, tparams2, res1, res2)
6379
case (ExistentialType(_, res1), _) if alwaysMatchSimple =>
6380
matchesType(res1, tp2, alwaysMatchSimple)
6381
case (_, ExistentialType(_, res2)) if alwaysMatchSimple =>
6382
matchesType(tp1, res2, alwaysMatchSimple)
6383
case (NullaryMethodType(rtp1), _) =>
6384
matchesType(rtp1, tp2, alwaysMatchSimple)
6385
case (_, NullaryMethodType(rtp2)) =>
6386
matchesType(tp1, rtp2, alwaysMatchSimple)
6387
case (MethodType(_, _), _) => false
6388
case (PolyType(_, _), _) => false
6389
case (_, MethodType(_, _)) => false
6390
case (_, PolyType(_, _)) => false
6392
alwaysMatchSimple || tp1 =:= tp2
6397
/** Are `syms1` and `syms2` parameter lists with pairwise equivalent types? */
6398
private def matchingParams(syms1: List[Symbol], syms2: List[Symbol], syms1isJava: Boolean, syms2isJava: Boolean): Boolean = syms1 match {
6401
case sym1 :: rest1 =>
6405
case sym2 :: rest2 =>
6409
syms1isJava && tp2.typeSymbol == ObjectClass && tp1.typeSymbol == AnyClass ||
6410
syms2isJava && tp1.typeSymbol == ObjectClass && tp2.typeSymbol == AnyClass) &&
6411
matchingParams(rest1, rest2, syms1isJava, syms2isJava)
6415
/** like map2, but returns list `xs` itself - instead of a copy - if function
6416
* `f` maps all elements to themselves.
6418
def map2Conserve[A <: AnyRef, B](xs: List[A], ys: List[B])(f: (A, B) => A): List[A] =
6421
val x1 = f(xs.head, ys.head)
6422
val xs1 = map2Conserve(xs.tail, ys.tail)(f)
6423
if ((x1 eq xs.head) && (xs1 eq xs.tail)) xs
6427
/** Solve constraint collected in types `tvars`.
6429
* @param tvars All type variables to be instantiated.
6430
* @param tparams The type parameters corresponding to `tvars`
6431
* @param variances The variances of type parameters; need to reverse
6432
* solution direction for all contravariant variables.
6433
* @param upper When `true` search for max solution else min.
6435
def solve(tvars: List[TypeVar], tparams: List[Symbol],
6436
variances: List[Int], upper: Boolean): Boolean =
6437
solve(tvars, tparams, variances, upper, AnyDepth)
6439
def solve(tvars: List[TypeVar], tparams: List[Symbol],
6440
variances: List[Int], upper: Boolean, depth: Int): Boolean = {
6442
def solveOne(tvar: TypeVar, tparam: Symbol, variance: Int) {
6443
if (tvar.constr.inst == NoType) {
6444
val up = if (variance != CONTRAVARIANT) upper else !upper
6445
tvar.constr.inst = null
6446
val bound: Type = if (up) tparam.info.bounds.hi else tparam.info.bounds.lo
6447
//Console.println("solveOne0(tv, tp, v, b)="+(tvar, tparam, variance, bound))
6448
var cyclic = bound contains tparam
6449
foreach3(tvars, tparams, variances)((tvar2, tparam2, variance2) => {
6450
val ok = (tparam2 != tparam) && (
6451
(bound contains tparam2)
6452
|| up && (tparam2.info.bounds.lo =:= tparam.tpeHK)
6453
|| !up && (tparam2.info.bounds.hi =:= tparam.tpeHK)
6456
if (tvar2.constr.inst eq null) cyclic = true
6457
solveOne(tvar2, tparam2, variance2)
6462
if (bound.typeSymbol != AnyClass) {
6463
log(s"$tvar addHiBound $bound.instantiateTypeParams($tparams, $tvars)")
6464
tvar addHiBound bound.instantiateTypeParams(tparams, tvars)
6466
for (tparam2 <- tparams)
6467
tparam2.info.bounds.lo.dealias match {
6468
case TypeRef(_, `tparam`, _) =>
6469
log(s"$tvar addHiBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)")
6470
tvar addHiBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars)
6474
if (bound.typeSymbol != NothingClass && bound.typeSymbol != tparam) {
6475
log(s"$tvar addLoBound $bound.instantiateTypeParams($tparams, $tvars)")
6476
tvar addLoBound bound.instantiateTypeParams(tparams, tvars)
6478
for (tparam2 <- tparams)
6479
tparam2.info.bounds.hi.dealias match {
6480
case TypeRef(_, `tparam`, _) =>
6481
log(s"$tvar addLoBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)")
6482
tvar addLoBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars)
6487
tvar.constr.inst = NoType // necessary because hibounds/lobounds may contain tvar
6489
//println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen)))
6492
if (depth != AnyDepth) glb(tvar.constr.hiBounds, depth) else glb(tvar.constr.hiBounds)
6494
if (depth != AnyDepth) lub(tvar.constr.loBounds, depth) else lub(tvar.constr.loBounds)
6497
log(s"$tvar setInst $newInst")
6498
tvar setInst newInst
6499
//Console.println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen))+" = "+tvar.constr.inst)//@MDEBUG
6503
// println("solving "+tvars+"/"+tparams+"/"+(tparams map (_.info)))
6504
foreach3(tvars, tparams, variances)(solveOne)
6505
tvars forall (tvar => tvar.constr.isWithinBounds(tvar.constr.inst))
6508
/** Do type arguments `targs` conform to formal parameters `tparams`?
6510
def isWithinBounds(pre: Type, owner: Symbol, tparams: List[Symbol], targs: List[Type]): Boolean = {
6511
var bounds = instantiatedBounds(pre, owner, tparams, targs)
6512
if (targs exists typeHasAnnotations)
6513
bounds = adaptBoundsToAnnotations(bounds, tparams, targs)
6514
(bounds corresponds targs)(boundsContainType)
6517
def instantiatedBounds(pre: Type, owner: Symbol, tparams: List[Symbol], targs: List[Type]): List[TypeBounds] =
6518
tparams map (_.info.asSeenFrom(pre, owner).instantiateTypeParams(tparams, targs).bounds)
6520
// Lubs and Glbs ---------------------------------------------------------
6522
private def printLubMatrix(btsMap: Map[Type, List[Type]], depth: Int) {
6523
import util.TableDef
6524
import TableDef.Column
6525
def str(tp: Type) = {
6526
if (tp == NoType) ""
6528
val s = ("" + tp).replaceAll("""[\w.]+\.(\w+)""", "$1")
6529
if (s.length < 60) s
6530
else (s take 57) + "..."
6534
val sorted = btsMap.toList.sortWith((x, y) => x._1.typeSymbol isLess y._1.typeSymbol)
6535
val maxSeqLength = sorted.map(_._2.size).max
6536
val padded = sorted map (_._2.padTo(maxSeqLength, NoType))
6537
val transposed = padded.transpose
6539
val columns: List[Column[List[Type]]] = mapWithIndex(sorted) {
6540
case ((k, v), idx) =>
6541
Column(str(k), (xs: List[Type]) => str(xs(idx)), true)
6544
val tableDef = TableDef(columns: _*)
6545
val formatted = tableDef.table(transposed)
6546
println("** Depth is " + depth + "\n" + formatted)
6549
/** From a list of types, find any which take type parameters
6550
* where the type parameter bounds contain references to other
6551
* any types in the list (including itself.)
6553
* @return List of symbol pairs holding the recursive type
6554
* parameter and the parameter which references it.
6556
def findRecursiveBounds(ts: List[Type]): List[(Symbol, Symbol)] = {
6559
val sym = ts.head.typeSymbol
6560
require(ts.tail forall (_.typeSymbol == sym), ts)
6561
for (p <- sym.typeParams ; in <- sym.typeParams ; if in.info.bounds contains p) yield
6566
/** Given a matrix `tsBts` whose columns are basetype sequences (and the symbols `tsParams` that should be interpreted as type parameters in this matrix),
6567
* compute its least sorted upwards closed upper bound relative to the following ordering <= between lists of types:
6569
* xs <= ys iff forall y in ys exists x in xs such that x <: y
6571
* @arg tsParams for each type in the original list of types `ts0`, its list of type parameters (if that type is a type constructor)
6572
* (these type parameters may be referred to by type arguments in the BTS column of those types,
6573
* and must be interpreted as bound variables; i.e., under a type lambda that wraps the types that refer to these type params)
6574
* @arg tsBts a matrix whose columns are basetype sequences
6575
* the first row is the original list of types for which we're computing the lub
6576
* (except that type constructors have been applied to their dummyArgs)
6577
* @See baseTypeSeq for a definition of sorted and upwards closed.
6579
private def lubList(ts: List[Type], depth: Int): List[Type] = {
6580
// Matching the type params of one of the initial types means dummies.
6581
val initialTypeParams = ts map (_.typeParams)
6582
def isHotForTs(xs: List[Type]) = initialTypeParams contains (xs map (_.typeSymbol))
6584
def elimHigherOrderTypeParam(tp: Type) = tp match {
6585
case TypeRef(pre, sym, args) if args.nonEmpty && isHotForTs(args) => tp.typeConstructor
6588
var lubListDepth = 0
6589
def loop(tsBts: List[List[Type]]): List[Type] = {
6592
if (tsBts.isEmpty || (tsBts exists typeListIsEmpty)) Nil
6593
else if (tsBts.tail.isEmpty) tsBts.head
6595
// ts0 is the 1-dimensional frontier of symbols cutting through 2-dimensional tsBts.
6596
// Invariant: all symbols "under" (closer to the first row) the frontier
6597
// are smaller (according to _.isLess) than the ones "on and beyond" the frontier
6598
val ts0 = tsBts map (_.head)
6600
// Is the frontier made up of types with the same symbol?
6601
val isUniformFrontier = (ts0: @unchecked) match {
6602
case t :: ts => ts forall (_.typeSymbol == t.typeSymbol)
6605
// Produce a single type for this frontier by merging the prefixes and arguments of those
6606
// typerefs that share the same symbol: that symbol is the current maximal symbol for which
6607
// the invariant holds, i.e., the one that conveys most information regarding subtyping. Before
6608
// merging, strip targs that refer to bound tparams (when we're computing the lub of type
6609
// constructors.) Also filter out all types that are a subtype of some other type.
6610
if (isUniformFrontier) {
6611
if (settings.debug.value || printLubs) {
6612
val fbounds = findRecursiveBounds(ts0)
6613
if (fbounds.nonEmpty) {
6614
println("Encountered " + fbounds.size + " recursive bounds while lubbing " + ts0.size + " types.")
6615
for ((p0, p1) <- fbounds) {
6616
val desc = if (p0 == p1) "its own bounds" else "the bounds of " + p1
6618
println(" " + p0.fullLocationString + " appears in " + desc)
6619
println(" " + p1 + " " + p1.info.bounds)
6624
val tails = tsBts map (_.tail)
6625
mergePrefixAndArgs(elimSub(ts0 map elimHigherOrderTypeParam, depth), 1, depth) match {
6626
case Some(tp) => tp :: loop(tails)
6627
case _ => loop(tails)
6631
// frontier is not uniform yet, move it beyond the current minimal symbol;
6632
// lather, rinSe, repeat
6633
val sym = minSym(ts0)
6634
val newtps = tsBts map (ts => if (ts.head.typeSymbol == sym) ts.tail else ts)
6636
val str = (newtps.zipWithIndex map { case (tps, idx) =>
6637
tps.map(" " + _ + "\n").mkString(" (" + idx + ")\n", "", "\n")
6640
println("Frontier(\n" + str + ")")
6641
printLubMatrix((ts zip tsBts).toMap, lubListDepth)
6649
val initialBTSes = ts map (_.baseTypeSeq.toList)
6651
printLubMatrix((ts zip initialBTSes).toMap, depth)
6656
/** The minimal symbol of a list of types (as determined by `Symbol.isLess`). */
6657
private def minSym(tps: List[Type]): Symbol =
6658
(tps.head.typeSymbol /: tps.tail) {
6659
(sym1, tp2) => if (tp2.typeSymbol isLess sym1) tp2.typeSymbol else sym1
6662
/** A minimal type list which has a given list of types as its base type sequence */
6663
def spanningTypes(ts: List[Type]): List[Type] = ts match {
6664
case List() => List()
6665
case first :: rest =>
6666
first :: spanningTypes(
6667
rest filter (t => !first.typeSymbol.isSubClass(t.typeSymbol)))
6670
/** Eliminate from list of types all elements which are a supertype
6671
* of some other element of the list. */
6672
private def elimSuper(ts: List[Type]): List[Type] = ts match {
6673
case List() => List()
6674
case List(t) => List(t)
6676
val rest = elimSuper(ts1 filter (t1 => !(t <:< t1)))
6677
if (rest exists (t1 => t1 <:< t)) rest else t :: rest
6680
def elimAnonymousClass(t: Type) = t match {
6681
case TypeRef(pre, clazz, Nil) if clazz.isAnonymousClass =>
6682
clazz.classBound.asSeenFrom(pre, clazz.owner)
6686
def elimRefinement(t: Type) = t match {
6687
case RefinedType(parents, decls) if !decls.isEmpty => intersectionType(parents)
6691
/** Eliminate from list of types all elements which are a subtype
6692
* of some other element of the list. */
6693
private def elimSub(ts: List[Type], depth: Int): List[Type] = {
6694
def elimSub0(ts: List[Type]): List[Type] = ts match {
6695
case List() => List()
6696
case List(t) => List(t)
6698
val rest = elimSub0(ts1 filter (t1 => !isSubType(t1, t, decr(depth))))
6699
if (rest exists (t1 => isSubType(t, t1, decr(depth)))) rest else t :: rest
6701
val ts0 = elimSub0(ts)
6702
if (ts0.isEmpty || ts0.tail.isEmpty) ts0
6704
val ts1 = ts0 mapConserve (t => elimAnonymousClass(t.dealiasWiden))
6706
else elimSub(ts1, depth)
6710
private def stripExistentialsAndTypeVars(ts: List[Type]): (List[Type], List[Symbol]) = {
6711
val quantified = ts flatMap {
6712
case ExistentialType(qs, _) => qs
6715
def stripType(tp: Type): Type = tp match {
6716
case ExistentialType(_, res) =>
6718
case tv@TypeVar(_, constr) =>
6719
if (tv.instValid) stripType(constr.inst)
6720
else if (tv.untouchable) tv
6721
else abort("trying to do lub/glb of typevar "+tp)
6724
val strippedTypes = ts mapConserve stripType
6725
(strippedTypes, quantified)
6728
def weakLub(ts: List[Type]) =
6729
if (ts.nonEmpty && (ts forall isNumericValueType)) (numericLub(ts), true)
6730
else if (ts exists typeHasAnnotations)
6731
(annotationsLub(lub(ts map (_.withoutAnnotations)), ts), true)
6732
else (lub(ts), false)
6734
def weakGlb(ts: List[Type]) = {
6735
if (ts.nonEmpty && (ts forall isNumericValueType)) {
6736
val nglb = numericGlb(ts)
6737
if (nglb != NoType) (nglb, true)
6738
else (glb(ts), false)
6739
} else if (ts exists typeHasAnnotations) {
6740
(annotationsGlb(glb(ts map (_.withoutAnnotations)), ts), true)
6741
} else (glb(ts), false)
6744
def numericLub(ts: List[Type]) =
6745
ts reduceLeft ((t1, t2) =>
6746
if (isNumericSubType(t1, t2)) t2
6747
else if (isNumericSubType(t2, t1)) t1
6750
def numericGlb(ts: List[Type]) =
6751
ts reduceLeft ((t1, t2) =>
6752
if (isNumericSubType(t1, t2)) t1
6753
else if (isNumericSubType(t2, t1)) t2
6756
def isWeakSubType(tp1: Type, tp2: Type) =
6757
tp1.deconst.normalize match {
6758
case TypeRef(_, sym1, _) if isNumericValueClass(sym1) =>
6759
tp2.deconst.normalize match {
6760
case TypeRef(_, sym2, _) if isNumericValueClass(sym2) =>
6761
isNumericSubClass(sym1, sym2)
6762
case tv2 @ TypeVar(_, _) =>
6763
tv2.registerBound(tp1, isLowerBound = true, isNumericBound = true)
6767
case tv1 @ TypeVar(_, _) =>
6768
tp2.deconst.normalize match {
6769
case TypeRef(_, sym2, _) if isNumericValueClass(sym2) =>
6770
tv1.registerBound(tp2, isLowerBound = false, isNumericBound = true)
6778
/** The isNumericValueType tests appear redundant, but without them
6779
* test/continuations-neg/function3.scala goes into an infinite loop.
6780
* (Even if the calls are to typeSymbolDirect.)
6782
def isNumericSubType(tp1: Type, tp2: Type): Boolean = (
6783
isNumericValueType(tp1)
6784
&& isNumericValueType(tp2)
6785
&& isNumericSubClass(tp1.typeSymbol, tp2.typeSymbol)
6788
private val lubResults = new mutable.HashMap[(Int, List[Type]), Type]
6789
private val glbResults = new mutable.HashMap[(Int, List[Type]), Type]
6791
def lub(ts: List[Type]): Type = ts match {
6792
case List() => NothingClass.tpe
6795
if (Statistics.canEnable) Statistics.incCounter(lubCount)
6796
val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, lubNanos) else null
6798
lub(ts, lubDepth(ts))
6802
if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
6806
/** The least upper bound wrt <:< of a list of types */
6807
private def lub(ts: List[Type], depth: Int): Type = {
6808
def lub0(ts0: List[Type]): Type = elimSub(ts0, depth) match {
6809
case List() => NothingClass.tpe
6811
case ts @ PolyType(tparams, _) :: _ =>
6812
val tparams1 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) =>
6813
tparam.cloneSymbol.setInfo(glb(bounds, depth)))
6814
PolyType(tparams1, lub0(matchingInstTypes(ts, tparams1)))
6815
case ts @ (mt @ MethodType(params, _)) :: rest =>
6816
MethodType(params, lub0(matchingRestypes(ts, mt.paramTypes)))
6817
case ts @ NullaryMethodType(_) :: rest =>
6818
NullaryMethodType(lub0(matchingRestypes(ts, Nil)))
6819
case ts @ TypeBounds(_, _) :: rest =>
6820
TypeBounds(glb(ts map (_.bounds.lo), depth), lub(ts map (_.bounds.hi), depth))
6821
case ts @ AnnotatedType(annots, tpe, _) :: rest =>
6822
annotationsLub(lub0(ts map (_.withoutAnnotations)), ts)
6824
lubResults get (depth, ts) match {
6825
case Some(lubType) =>
6828
lubResults((depth, ts)) = AnyClass.tpe
6829
val res = if (depth < 0) AnyClass.tpe else lub1(ts)
6830
lubResults((depth, ts)) = res
6834
def lub1(ts0: List[Type]): Type = {
6835
val (ts, tparams) = stripExistentialsAndTypeVars(ts0)
6836
val lubBaseTypes: List[Type] = lubList(ts, depth)
6837
val lubParents = spanningTypes(lubBaseTypes)
6838
val lubOwner = commonOwner(ts)
6839
val lubBase = intersectionType(lubParents, lubOwner)
6841
if (phase.erasedTypes || depth == 0) lubBase
6843
val lubRefined = refinedType(lubParents, lubOwner)
6844
val lubThisType = lubRefined.typeSymbol.thisType
6845
val narrowts = ts map (_.narrow)
6846
def excludeFromLub(sym: Symbol) = (
6848
|| sym.isConstructor
6851
|| narrowts.exists(t => !refines(t, sym))
6853
def lubsym(proto: Symbol): Symbol = {
6854
val prototp = lubThisType.memberInfo(proto)
6855
val syms = narrowts map (t =>
6856
t.nonPrivateMember(proto.name).suchThat(sym =>
6857
sym.tpe matches prototp.substThis(lubThisType.typeSymbol, t)))
6858
if (syms contains NoSymbol) NoSymbol
6861
map2(narrowts, syms)((t, sym) => t.memberInfo(sym).substThis(t.typeSymbol, lubThisType))
6862
if (proto.isTerm) // possible problem: owner of info is still the old one, instead of new refinement class
6863
proto.cloneSymbol(lubRefined.typeSymbol).setInfoOwnerAdjusted(lub(symtypes, decr(depth)))
6864
else if (symtypes.tail forall (symtypes.head =:= _))
6865
proto.cloneSymbol(lubRefined.typeSymbol).setInfoOwnerAdjusted(symtypes.head)
6867
def lubBounds(bnds: List[TypeBounds]): TypeBounds =
6868
TypeBounds(glb(bnds map (_.lo), decr(depth)), lub(bnds map (_.hi), decr(depth)))
6869
lubRefined.typeSymbol.newAbstractType(proto.name.toTypeName, proto.pos)
6870
.setInfoOwnerAdjusted(lubBounds(symtypes map (_.bounds)))
6874
def refines(tp: Type, sym: Symbol): Boolean = {
6875
val syms = tp.nonPrivateMember(sym.name).alternatives;
6876
!syms.isEmpty && (syms forall (alt =>
6877
// todo alt != sym is strictly speaking not correct, but without it we lose
6879
alt != sym && !specializesSym(lubThisType, sym, tp, alt, depth)))
6881
// add a refinement symbol for all non-class members of lubBase
6882
// which are refined by every type in ts.
6883
for (sym <- lubBase.nonPrivateMembers ; if !excludeFromLub(sym)) {
6885
val lsym = lubsym(sym)
6886
if (lsym != NoSymbol) addMember(lubThisType, lubRefined, lsym, depth)
6888
case ex: NoCommonType =>
6891
if (lubRefined.decls.isEmpty) lubBase
6892
else if (!verifyLubs) lubRefined
6894
// Verify that every given type conforms to the calculated lub.
6895
// In theory this should not be necessary, but higher-order type
6896
// parameters are not handled correctly.
6897
val ok = ts forall { t =>
6898
isSubType(t, lubRefined, depth) || {
6899
if (settings.debug.value || printLubs) {
6901
"Malformed lub: " + lubRefined + "\n" +
6902
"Argument " + t + " does not conform. Falling back to " + lubBase
6908
// If not, fall back on the more conservative calculation.
6913
// dropRepeatedParamType is a localized fix for SI-6897. We should probably
6914
// integrate that transformation at a lower level in master, but lubs are
6915
// the likely and maybe only spot they escape, so fixing here for 2.10.1.
6916
existentialAbstraction(tparams, dropRepeatedParamType(lubType))
6919
println(indent + "lub of " + ts + " at depth "+depth)//debug
6920
indent = indent + " "
6921
assert(indent.length <= 100)
6923
if (Statistics.canEnable) Statistics.incCounter(nestedLubCount)
6926
indent = indent stripSuffix " "
6927
println(indent + "lub of " + ts + " is " + res)//debug
6929
if (ts forall typeIsNotNull) res.notNull else res
6932
val GlbFailure = new Throwable
6934
/** A global counter for glb calls in the `specializes` query connected to the `addMembers`
6935
* call in `glb`. There's a possible infinite recursion when `specializes` calls
6936
* memberType, which calls baseTypeSeq, which calls mergePrefixAndArgs, which calls glb.
6937
* The counter breaks this recursion after two calls.
6938
* If the recursion is broken, no member is added to the glb.
6940
private var globalGlbDepth = 0
6941
private final val globalGlbLimit = 2
6943
/** The greatest lower bound of a list of types (as determined by `<:<`). */
6944
def glb(ts: List[Type]): Type = elimSuper(ts) match {
6945
case List() => AnyClass.tpe
6948
if (Statistics.canEnable) Statistics.incCounter(lubCount)
6949
val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, lubNanos) else null
6951
glbNorm(ts0, lubDepth(ts0))
6955
if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start)
6959
private def glb(ts: List[Type], depth: Int): Type = elimSuper(ts) match {
6960
case List() => AnyClass.tpe
6962
case ts0 => glbNorm(ts0, depth)
6965
/** The greatest lower bound of a list of types (as determined by `<:<`), which have been normalized
6966
* with regard to `elimSuper`. */
6967
protected def glbNorm(ts: List[Type], depth: Int): Type = {
6968
def glb0(ts0: List[Type]): Type = ts0 match {
6969
case List() => AnyClass.tpe
6971
case ts @ PolyType(tparams, _) :: _ =>
6972
val tparams1 = map2(tparams, matchingBounds(ts, tparams).transpose)((tparam, bounds) =>
6973
tparam.cloneSymbol.setInfo(lub(bounds, depth)))
6974
PolyType(tparams1, glbNorm(matchingInstTypes(ts, tparams1), depth))
6975
case ts @ (mt @ MethodType(params, _)) :: rest =>
6976
MethodType(params, glbNorm(matchingRestypes(ts, mt.paramTypes), depth))
6977
case ts @ NullaryMethodType(_) :: rest =>
6978
NullaryMethodType(glbNorm(matchingRestypes(ts, Nil), depth))
6979
case ts @ TypeBounds(_, _) :: rest =>
6980
TypeBounds(lub(ts map (_.bounds.lo), depth), glb(ts map (_.bounds.hi), depth))
6982
glbResults get (depth, ts) match {
6983
case Some(glbType) =>
6986
glbResults((depth, ts)) = NothingClass.tpe
6987
val res = if (depth < 0) NothingClass.tpe else glb1(ts)
6988
glbResults((depth, ts)) = res
6992
def glb1(ts0: List[Type]): Type = {
6994
val (ts, tparams) = stripExistentialsAndTypeVars(ts0)
6995
val glbOwner = commonOwner(ts)
6996
def refinedToParents(t: Type): List[Type] = t match {
6997
case RefinedType(ps, _) => ps flatMap refinedToParents
7000
def refinedToDecls(t: Type): List[Scope] = t match {
7001
case RefinedType(ps, decls) =>
7002
val dss = ps flatMap refinedToDecls
7003
if (decls.isEmpty) dss else decls :: dss
7006
val ts1 = ts flatMap refinedToParents
7007
val glbBase = intersectionType(ts1, glbOwner)
7009
if (phase.erasedTypes || depth == 0) glbBase
7011
val glbRefined = refinedType(ts1, glbOwner)
7012
val glbThisType = glbRefined.typeSymbol.thisType
7013
def glbsym(proto: Symbol): Symbol = {
7014
val prototp = glbThisType.memberInfo(proto)
7015
val syms = for (t <- ts;
7016
alt <- (t.nonPrivateMember(proto.name).alternatives);
7017
if glbThisType.memberInfo(alt) matches prototp
7019
val symtypes = syms map glbThisType.memberInfo
7020
assert(!symtypes.isEmpty)
7021
proto.cloneSymbol(glbRefined.typeSymbol).setInfoOwnerAdjusted(
7022
if (proto.isTerm) glb(symtypes, decr(depth))
7024
def isTypeBound(tp: Type) = tp match {
7025
case TypeBounds(_, _) => true
7028
def glbBounds(bnds: List[Type]): TypeBounds = {
7029
val lo = lub(bnds map (_.bounds.lo), decr(depth))
7030
val hi = glb(bnds map (_.bounds.hi), decr(depth))
7031
if (lo <:< hi) TypeBounds(lo, hi)
7032
else throw GlbFailure
7034
val symbounds = symtypes filter isTypeBound
7036
if (symbounds.isEmpty)
7038
else glbBounds(symbounds)
7039
for (t <- symtypes if !isTypeBound(t))
7040
if (result.bounds containsType t) result = t
7041
else throw GlbFailure
7045
if (globalGlbDepth < globalGlbLimit)
7048
val dss = ts flatMap refinedToDecls
7049
for (ds <- dss; sym <- ds.iterator)
7050
if (globalGlbDepth < globalGlbLimit && !specializesSym(glbThisType, sym, depth))
7052
addMember(glbThisType, glbRefined, glbsym(sym), depth)
7054
case ex: NoCommonType =>
7059
if (glbRefined.decls.isEmpty) glbBase else glbRefined
7061
existentialAbstraction(tparams, glbType)
7064
if (ts forall (t => NullClass.tpe <:< t)) NullClass.tpe
7065
else NothingClass.tpe
7068
// if (settings.debug.value) { println(indent + "glb of " + ts + " at depth "+depth); indent = indent + " " } //DEBUG
7070
if (Statistics.canEnable) Statistics.incCounter(nestedLubCount)
7073
// if (settings.debug.value) { indent = indent.substring(0, indent.length() - 2); log(indent + "glb of " + ts + " is " + res) }//DEBUG
7075
if (ts exists typeIsNotNull) res.notNull else res
7078
/** A list of the typevars in a type. */
7079
def typeVarsInType(tp: Type): List[TypeVar] = {
7080
var tvs: List[TypeVar] = Nil
7082
case t: TypeVar => tvs ::= t
7087
/** Make each type var in this type use its original type for comparisons instead
7088
* of collecting constraints.
7090
def suspendTypeVarsInType(tp: Type): List[TypeVar] = {
7091
val tvs = typeVarsInType(tp)
7092
// !!! Is it somehow guaranteed that this will not break under nesting?
7093
// In general one has to save and restore the contents of the field...
7094
tvs foreach (_.suspended = true)
7098
/** Compute lub (if `variance == 1`) or glb (if `variance == -1`) of given list
7099
* of types `tps`. All types in `tps` are typerefs or singletypes
7100
* with the same symbol.
7101
* Return `Some(x)` if the computation succeeds with result `x`.
7102
* Return `None` if the computation fails.
7104
def mergePrefixAndArgs(tps: List[Type], variance: Int, depth: Int): Option[Type] = tps match {
7107
case TypeRef(_, sym, _) :: rest =>
7108
val pres = tps map (_.prefix) // prefix normalizes automatically
7109
val pre = if (variance == 1) lub(pres, depth) else glb(pres, depth)
7110
val argss = tps map (_.normalize.typeArgs) // symbol equality (of the tp in tps) was checked using typeSymbol, which normalizes, so should normalize before retrieving arguments
7111
val capturedParams = new ListBuffer[Symbol]
7113
if (sym == ArrayClass && phase.erasedTypes) {
7114
// special treatment for lubs of array types after erasure:
7115
// if argss contain one value type and some other type, the lub is Object
7116
// if argss contain several reference types, the lub is an array over lub of argtypes
7117
if (argss exists typeListIsEmpty) {
7118
None // something is wrong: an array without a type arg.
7120
val args = argss map (_.head)
7121
if (args.tail forall (_ =:= args.head)) Some(typeRef(pre, sym, List(args.head)))
7122
else if (args exists (arg => isPrimitiveValueClass(arg.typeSymbol))) Some(ObjectClass.tpe)
7123
else Some(typeRef(pre, sym, List(lub(args))))
7126
else transposeSafe(argss) match {
7128
// transpose freaked out because of irregular argss
7129
// catching just in case (shouldn't happen, but also doesn't cost us)
7130
// [JZ] It happens: see SI-5683.
7131
debuglog("transposed irregular matrix!?" +(tps, argss))
7133
case Some(argsst) =>
7134
val args = map2(sym.typeParams, argsst) { (tparam, as) =>
7136
if (tparam.variance == variance) {
7137
// Take the intersection of the upper bounds of the type parameters
7138
// rather than falling all the way back to "Any", otherwise we end up not
7139
// conforming to bounds.
7140
val bounds0 = sym.typeParams map (_.info.bounds.hi) filterNot (_.typeSymbol == AnyClass)
7141
if (bounds0.isEmpty) AnyClass.tpe
7142
else intersectionType(bounds0 map (b => b.asSeenFrom(tps.head, sym)))
7144
else if (tparam.variance == -variance) NothingClass.tpe
7148
if (tparam.variance == variance) lub(as, decr(depth))
7149
else if (tparam.variance == -variance) glb(as, decr(depth))
7151
val l = lub(as, decr(depth))
7152
val g = glb(as, decr(depth))
7154
else { // Martin: I removed this, because incomplete. Not sure there is a good way to fix it. For the moment we
7155
// just err on the conservative side, i.e. with a bound that is too high.
7156
// if(!(tparam.info.bounds contains tparam)) //@M can't deal with f-bounds, see #2251
7158
val qvar = commonOwner(as) freshExistential "" setInfo TypeBounds(g, l)
7159
capturedParams += qvar
7165
if (args contains NoType) None
7166
else Some(existentialAbstraction(capturedParams.toList, typeRef(pre, sym, args)))
7169
case ex: MalformedType => None
7171
case SingleType(_, sym) :: rest =>
7172
val pres = tps map (_.prefix)
7173
val pre = if (variance == 1) lub(pres, depth) else glb(pres, depth)
7175
Some(singleType(pre, sym))
7177
case ex: MalformedType => None
7179
case ExistentialType(tparams, quantified) :: rest =>
7180
mergePrefixAndArgs(quantified :: rest, variance, depth) map (existentialAbstraction(tparams, _))
7182
abort(s"mergePrefixAndArgs($tps, $variance, $depth): unsupported tps")
7185
def addMember(thistp: Type, tp: Type, sym: Symbol): Unit = addMember(thistp, tp, sym, AnyDepth)
7187
/** Make symbol `sym` a member of scope `tp.decls`
7188
* where `thistp` is the narrowed owner type of the scope.
7190
def addMember(thistp: Type, tp: Type, sym: Symbol, depth: Int) {
7191
assert(sym != NoSymbol)
7192
// debuglog("add member " + sym+":"+sym.info+" to "+thistp) //DEBUG
7193
if (!specializesSym(thistp, sym, depth)) {
7195
for (alt <- tp.nonPrivateDecl(sym.name).alternatives)
7196
if (specializesSym(thistp, sym, thistp, alt, depth))
7197
tp.decls unlink alt;
7202
def isJavaVarargsAncestor(clazz: Symbol) = (
7204
&& clazz.isJavaDefined
7205
&& (clazz.info.nonPrivateDecls exists isJavaVarArgsMethod)
7207
def inheritsJavaVarArgsMethod(clazz: Symbol) =
7208
clazz.thisType.baseClasses exists isJavaVarargsAncestor
7210
/** All types in list must be polytypes with type parameter lists of
7211
* same length as tparams.
7212
* Returns list of list of bounds infos, where corresponding type
7213
* parameters are renamed to tparams.
7215
private def matchingBounds(tps: List[Type], tparams: List[Symbol]): List[List[Type]] = {
7216
def getBounds(tp: Type): List[Type] = tp match {
7217
case PolyType(tparams1, _) if sameLength(tparams1, tparams) =>
7218
tparams1 map (tparam => tparam.info.substSym(tparams1, tparams))
7220
if (tp ne tp.normalize) getBounds(tp.normalize)
7221
else throw new NoCommonType(tps)
7226
/** All types in list must be polytypes with type parameter lists of
7227
* same length as tparams.
7228
* Returns list of instance types, where corresponding type
7229
* parameters are renamed to tparams.
7231
private def matchingInstTypes(tps: List[Type], tparams: List[Symbol]): List[Type] = {
7232
def transformResultType(tp: Type): Type = tp match {
7233
case PolyType(tparams1, restpe) if sameLength(tparams1, tparams) =>
7234
restpe.substSym(tparams1, tparams)
7236
if (tp ne tp.normalize) transformResultType(tp.normalize)
7237
else throw new NoCommonType(tps)
7239
tps map transformResultType
7242
/** All types in list must be method types with equal parameter types.
7243
* Returns list of their result types.
7245
private def matchingRestypes(tps: List[Type], pts: List[Type]): List[Type] =
7247
case mt @ MethodType(params1, res) if isSameTypes(mt.paramTypes, pts) =>
7249
case NullaryMethodType(res) if pts.isEmpty =>
7252
throw new NoCommonType(tps)
7255
// Errors and Diagnostics -----------------------------------------------------
7257
/** A throwable signalling a type error */
7258
class TypeError(var pos: Position, val msg: String) extends Throwable(msg) {
7259
def this(msg: String) = this(NoPosition, msg)
7262
// TODO: RecoverableCyclicReference should be separated from TypeError,
7263
// but that would be a big change. Left for further refactoring.
7264
/** An exception for cyclic references from which we can recover */
7265
case class RecoverableCyclicReference(sym: Symbol)
7266
extends TypeError("illegal cyclic reference involving " + sym) {
7267
if (settings.debug.value) printStackTrace()
7270
class NoCommonType(tps: List[Type]) extends Throwable(
7271
"lub/glb of incompatible types: " + tps.mkString("", " and ", "")) with ControlThrowable
7273
/** A throwable signalling a malformed type */
7274
class MalformedType(msg: String) extends TypeError(msg) {
7275
def this(pre: Type, tp: String) = this("malformed type: " + pre + "#" + tp)
7278
/** The current indentation string for traces */
7279
private var indent: String = ""
7281
/** Perform operation `p` on arguments `tp1`, `arg2` and print trace of computation. */
7282
protected def explain[T](op: String, p: (Type, T) => Boolean, tp1: Type, arg2: T): Boolean = {
7283
Console.println(indent + tp1 + " " + op + " " + arg2 + "?" /* + "("+tp1.getClass+","+arg2.getClass+")"*/)
7284
indent = indent + " "
7285
val result = p(tp1, arg2)
7286
indent = indent stripSuffix " "
7287
Console.println(indent + result)
7291
/** If option `explaintypes` is set, print a subtype trace for `found <:< required`. */
7292
def explainTypes(found: Type, required: Type) {
7293
if (settings.explaintypes.value) withTypesExplained(found <:< required)
7296
/** If option `explaintypes` is set, print a subtype trace for `op(found, required)`. */
7297
def explainTypes(op: (Type, Type) => Any, found: Type, required: Type) {
7298
if (settings.explaintypes.value) withTypesExplained(op(found, required))
7301
/** Execute `op` while printing a trace of the operations on types executed. */
7302
def withTypesExplained[A](op: => A): A = {
7303
val s = explainSwitch
7304
try { explainSwitch = true; op } finally { explainSwitch = s }
7307
def isUnboundedGeneric(tp: Type) = tp match {
7308
case t @ TypeRef(_, sym, _) => sym.isAbstractType && !(t <:< AnyRefClass.tpe)
7311
def isBoundedGeneric(tp: Type) = tp match {
7312
case TypeRef(_, sym, _) if sym.isAbstractType => (tp <:< AnyRefClass.tpe)
7313
case TypeRef(_, sym, _) => !isPrimitiveValueClass(sym)
7316
// Add serializable to a list of parents, unless one of them already is
7317
def addSerializable(ps: Type*): List[Type] = (
7318
if (ps exists typeIsSubTypeOfSerializable) ps.toList
7319
else (ps :+ SerializableClass.tpe).toList
7322
/** Adds the @uncheckedBound annotation if the given `tp` has type arguments */
7323
final def uncheckedBounds(tp: Type): Type = {
7324
if (tp.typeArgs.isEmpty || UncheckedBoundsClass == NoSymbol) tp // second condition for backwards compatibilty with older scala-reflect.jar
7325
else tp.withAnnotation(AnnotationInfo marker UncheckedBoundsClass.tpe)
7328
/** Members of the given class, other than those inherited
7329
* from Any or AnyRef.
7331
def nonTrivialMembers(clazz: Symbol): Iterable[Symbol] =
7332
clazz.info.members filterNot (sym => sym.owner == ObjectClass || sym.owner == AnyClass)
7334
def objToAny(tp: Type): Type =
7335
if (!phase.erasedTypes && tp.typeSymbol == ObjectClass) AnyClass.tpe
7338
val shorthands = Set(
7339
"scala.collection.immutable.List",
7340
"scala.collection.immutable.Nil",
7341
"scala.collection.Seq",
7342
"scala.collection.Traversable",
7343
"scala.collection.Iterable",
7344
"scala.collection.mutable.StringBuilder",
7345
"scala.collection.IndexedSeq",
7346
"scala.collection.Iterator")
7349
/** The maximum number of recursions allowed in toString
7351
final val maxTostringRecursions = 50
7353
private var tostringRecursions = 0
7355
protected def typeToString(tpe: Type): String =
7356
if (tostringRecursions >= maxTostringRecursions) {
7357
debugwarn("Exceeded recursion depth attempting to print type.")
7358
if (settings.debug.value)
7359
(new Throwable).printStackTrace
7365
tostringRecursions += 1
7368
tostringRecursions -= 1
7371
// ----- Hoisted closures and convenience methods, for compile time reductions -------
7373
private[scala] val typeIsNotNull = (tp: Type) => tp.isNotNull
7374
private[scala] val isTypeVar = (tp: Type) => tp.isInstanceOf[TypeVar]
7375
private[scala] val typeContainsTypeVar = (tp: Type) => tp exists isTypeVar
7376
private[scala] val typeIsNonClassType = (tp: Type) => tp.typeSymbolDirect.isNonClassType
7377
private[scala] val typeIsExistentiallyBound = (tp: Type) => tp.typeSymbol.isExistentiallyBound
7378
private[scala] val typeIsErroneous = (tp: Type) => tp.isErroneous
7379
private[scala] val typeIsError = (tp: Type) => tp.isError
7380
private[scala] val typeHasAnnotations = (tp: Type) => tp.annotations.nonEmpty
7381
private[scala] val boundsContainType = (bounds: TypeBounds, tp: Type) => bounds containsType tp
7382
private[scala] val typeListIsEmpty = (ts: List[Type]) => ts.isEmpty
7383
private[scala] val typeIsSubTypeOfSerializable = (tp: Type) => tp <:< SerializableClass.tpe
7384
private[scala] val typeIsNothing = (tp: Type) => tp.typeSymbolDirect eq NothingClass
7385
private[scala] val typeIsAny = (tp: Type) => tp.typeSymbolDirect eq AnyClass
7386
private[scala] val typeIsHigherKinded = (tp: Type) => tp.isHigherKinded
7388
@tailrec private def typesContain(tps: List[Type], sym: Symbol): Boolean = tps match {
7389
case tp :: rest => (tp contains sym) || typesContain(rest, sym)
7393
@tailrec private def areTrivialTypes(tps: List[Type]): Boolean = tps match {
7394
case tp :: rest => tp.isTrivial && areTrivialTypes(rest)
7398
// -------------- Classtags --------------------------------------------------------
7400
implicit val AnnotatedTypeTag = ClassTag[AnnotatedType](classOf[AnnotatedType])
7401
implicit val BoundedWildcardTypeTag = ClassTag[BoundedWildcardType](classOf[BoundedWildcardType])
7402
implicit val ClassInfoTypeTag = ClassTag[ClassInfoType](classOf[ClassInfoType])
7403
implicit val CompoundTypeTag = ClassTag[CompoundType](classOf[CompoundType])
7404
implicit val ConstantTypeTag = ClassTag[ConstantType](classOf[ConstantType])
7405
implicit val ExistentialTypeTag = ClassTag[ExistentialType](classOf[ExistentialType])
7406
implicit val MethodTypeTag = ClassTag[MethodType](classOf[MethodType])
7407
implicit val NullaryMethodTypeTag = ClassTag[NullaryMethodType](classOf[NullaryMethodType])
7408
implicit val PolyTypeTag = ClassTag[PolyType](classOf[PolyType])
7409
implicit val RefinedTypeTag = ClassTag[RefinedType](classOf[RefinedType])
7410
implicit val SingletonTypeTag = ClassTag[SingletonType](classOf[SingletonType])
7411
implicit val SingleTypeTag = ClassTag[SingleType](classOf[SingleType])
7412
implicit val SuperTypeTag = ClassTag[SuperType](classOf[SuperType])
7413
implicit val ThisTypeTag = ClassTag[ThisType](classOf[ThisType])
7414
implicit val TypeBoundsTag = ClassTag[TypeBounds](classOf[TypeBounds])
7415
implicit val TypeRefTag = ClassTag[TypeRef](classOf[TypeRef])
7416
implicit val TypeTagg = ClassTag[Type](classOf[Type])
7418
// -------------- Statistics --------------------------------------------------------
7420
Statistics.newView("#unique types") { if (uniques == null) 0 else uniques.size }
7425
import BaseTypeSeqsStats._
7426
val rawTypeCount = Statistics.newCounter ("#raw type creations")
7427
val asSeenFromCount = Statistics.newCounter ("#asSeenFrom ops")
7428
val subtypeCount = Statistics.newCounter ("#subtype ops")
7429
val sametypeCount = Statistics.newCounter ("#sametype ops")
7430
val lubCount = Statistics.newCounter ("#toplevel lubs/glbs")
7431
val nestedLubCount = Statistics.newCounter ("#all lubs/glbs")
7432
val findMemberCount = Statistics.newCounter ("#findMember ops")
7433
val findMembersCount = Statistics.newCounter ("#findMembers ops")
7434
val noMemberCount = Statistics.newSubCounter(" of which not found", findMemberCount)
7435
val multMemberCount = Statistics.newSubCounter(" of which multiple overloaded", findMemberCount)
7436
val typerNanos = Statistics.newTimer ("time spent typechecking", "typer")
7437
val lubNanos = Statistics.newStackableTimer("time spent in lubs", typerNanos)
7438
val subtypeNanos = Statistics.newStackableTimer("time spent in <:<", typerNanos)
7439
val findMemberNanos = Statistics.newStackableTimer("time spent in findmember", typerNanos)
7440
val findMembersNanos = Statistics.newStackableTimer("time spent in findmembers", typerNanos)
7441
val asSeenFromNanos = Statistics.newStackableTimer("time spent in asSeenFrom", typerNanos)
7442
val baseTypeSeqNanos = Statistics.newStackableTimer("time spent in baseTypeSeq", typerNanos)
7443
val baseClassesNanos = Statistics.newStackableTimer("time spent in baseClasses", typerNanos)
7444
val compoundBaseTypeSeqCount = Statistics.newSubCounter(" of which for compound types", baseTypeSeqCount)
7445
val typerefBaseTypeSeqCount = Statistics.newSubCounter(" of which for typerefs", baseTypeSeqCount)
7446
val singletonBaseTypeSeqCount = Statistics.newSubCounter(" of which for singletons", baseTypeSeqCount)
7447
val typeOpsStack = Statistics.newTimerStack()
7449
/** Commented out, because right now this does not inline, so creates a closure which will distort statistics
7450
@inline final def timedTypeOp[T](c: Statistics.StackableTimer)(op: => T): T = {
7451
val start = Statistics.pushTimer(typeOpsStack, c)