diff options
author | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2012-10-02 09:03:00 -0700 |
---|---|---|
committer | Grzegorz Kossakowski <grzegorz.kossakowski@gmail.com> | 2012-10-02 09:03:00 -0700 |
commit | 5dae38df7d8929a4666c9263cc78579bed972ac2 (patch) | |
tree | 4abc99a579fe9977950ef3ed8d7bc84d3cb971a3 /src | |
parent | e93ca3231798241baf0f48ad361c0aa9668ee871 (diff) | |
parent | 81226b82d8c8b138eabb6956cab82410a17d812c (diff) | |
download | scala-5dae38df7d8929a4666c9263cc78579bed972ac2.tar.gz scala-5dae38df7d8929a4666c9263cc78579bed972ac2.tar.bz2 scala-5dae38df7d8929a4666c9263cc78579bed972ac2.zip |
Merge pull request #1437 from paulp/typevar-suspension
Typevar suspension
Diffstat (limited to 'src')
-rw-r--r-- | src/reflect/scala/reflect/internal/Types.scala | 409 |
1 files changed, 204 insertions, 205 deletions
diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index 0f26ea00ea..876ae53da0 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -1037,69 +1037,66 @@ trait Types extends api.Types { self: SymbolTable => } def findMembers(excludedFlags: Long, requiredFlags: Long): Scope = { - // if this type contains type variables, put them to sleep for a while -- don't just wipe them out by - // replacing them by the corresponding type parameter, as that messes up (e.g.) type variables in type refinements - // without this, the matchesType call would lead to type variables on both sides - // of a subtyping/equality judgement, which can lead to recursive types being constructed. - // See (t0851) for a situation where this happens. - val suspension: List[TypeVar] = if (this.isGround) null else suspendTypeVarsInType(this) - - if (Statistics.canEnable) Statistics.incCounter(findMembersCount) - val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, findMembersNanos) else null - - //Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG - var members: Scope = null - var required = requiredFlags - var excluded = excludedFlags | DEFERRED - var continue = true - var self: Type = null - while (continue) { - continue = false - val bcs0 = baseClasses - var bcs = bcs0 - while (!bcs.isEmpty) { - val decls = bcs.head.info.decls - var entry = decls.elems - while (entry ne null) { - val sym = entry.sym - val flags = sym.flags - if ((flags & required) == required) { - val excl = flags & excluded - if (excl == 0L && - (// omit PRIVATE LOCALS unless selector class is contained in class owning the def. - (bcs eq bcs0) || - (flags & PrivateLocal) != PrivateLocal || - (bcs0.head.hasTransOwner(bcs.head)))) { - if (members eq null) members = newFindMemberScope - var others: ScopeEntry = members.lookupEntry(sym.name) - var symtpe: Type = null - while ((others ne null) && { - val other = others.sym - (other ne sym) && - ((other.owner eq sym.owner) || - (flags & PRIVATE) != 0 || { - if (self eq null) self = this.narrow - if (symtpe eq null) symtpe = self.memberType(sym) - !(self.memberType(other) matches symtpe) - })}) { - others = members lookupNextEntry others + def findMembersInternal: Scope = { + var members: Scope = null + if (Statistics.canEnable) Statistics.incCounter(findMembersCount) + val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, findMembersNanos) else null + + //Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG + var required = requiredFlags + var excluded = excludedFlags | DEFERRED + var continue = true + var self: Type = null + while (continue) { + continue = false + val bcs0 = baseClasses + var bcs = bcs0 + while (!bcs.isEmpty) { + val decls = bcs.head.info.decls + var entry = decls.elems + while (entry ne null) { + val sym = entry.sym + val flags = sym.flags + if ((flags & required) == required) { + val excl = flags & excluded + if (excl == 0L && + (// omit PRIVATE LOCALS unless selector class is contained in class owning the def. + (bcs eq bcs0) || + (flags & PrivateLocal) != PrivateLocal || + (bcs0.head.hasTransOwner(bcs.head)))) { + if (members eq null) members = newFindMemberScope + var others: ScopeEntry = members.lookupEntry(sym.name) + var symtpe: Type = null + while ((others ne null) && { + val other = others.sym + (other ne sym) && + ((other.owner eq sym.owner) || + (flags & PRIVATE) != 0 || { + if (self eq null) self = this.narrow + if (symtpe eq null) symtpe = self.memberType(sym) + !(self.memberType(other) matches symtpe) + })}) { + others = members lookupNextEntry others + } + if (others eq null) members enter sym + } else if (excl == DEFERRED) { + continue = true } - if (others eq null) members enter sym - } else if (excl == DEFERRED) { - continue = true } - } - entry = entry.next - } // while (entry ne null) - // excluded = excluded | LOCAL - bcs = bcs.tail - } // while (!bcs.isEmpty) - required |= DEFERRED - excluded &= ~(DEFERRED.toLong) - } // while (continue) - if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) - if (suspension ne null) suspension foreach (_.suspended = false) - if (members eq null) EmptyScope else members + entry = entry.next + } // while (entry ne null) + // excluded = excluded | LOCAL + bcs = bcs.tail + } // while (!bcs.isEmpty) + required |= DEFERRED + excluded &= ~(DEFERRED.toLong) + } // while (continue) + if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) + if (members eq null) EmptyScope else members + } + + if (this.isGround) findMembersInternal + else suspendingTypeVars(typeVarsInType(this))(findMembersInternal) } /** @@ -1113,102 +1110,98 @@ trait Types extends api.Types { self: SymbolTable => */ //TODO: use narrow only for modules? (correct? efficiency gain?) def findMember(name: Name, excludedFlags: Long, requiredFlags: Long, stableOnly: Boolean): Symbol = { - // if this type contains type variables, put them to sleep for a while -- don't just wipe them out by - // replacing them by the corresponding type parameter, as that messes up (e.g.) type variables in type refinements - // without this, the matchesType call would lead to type variables on both sides - // of a subtyping/equality judgement, which can lead to recursive types being constructed. - // See (t0851) for a situation where this happens. - val suspension: List[TypeVar] = if (this.isGround) null else suspendTypeVarsInType(this) - - if (Statistics.canEnable) Statistics.incCounter(findMemberCount) - val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, findMemberNanos) else null - - //Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG - var member: Symbol = NoSymbol - var members: List[Symbol] = null - var lastM: ::[Symbol] = null - var membertpe: Type = null - var required = requiredFlags - var excluded = excludedFlags | DEFERRED - var continue = true - var self: Type = null - - while (continue) { - continue = false - val bcs0 = baseClasses - var bcs = bcs0 - while (!bcs.isEmpty) { - val decls = bcs.head.info.decls - var entry = decls.lookupEntry(name) - while (entry ne null) { - val sym = entry.sym - val flags = sym.flags - if ((flags & required) == required) { - val excl = flags & excluded - if (excl == 0L && - (// omit PRIVATE LOCALS unless selector class is contained in class owning the def. - (bcs eq bcs0) || - (flags & PrivateLocal) != PrivateLocal || - (bcs0.head.hasTransOwner(bcs.head)))) { - if (name.isTypeName || stableOnly && sym.isStable) { - if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) - if (suspension ne null) suspension foreach (_.suspended = false) - return sym - } else if (member eq NoSymbol) { - member = sym - } else if (members eq null) { - if ((member ne sym) && - ((member.owner eq sym.owner) || - (flags & PRIVATE) != 0 || { - if (self eq null) self = this.narrow - if (membertpe eq null) membertpe = self.memberType(member) - !(membertpe matches self.memberType(sym)) - })) { - lastM = new ::(sym, null) - members = member :: lastM - } - } else { - var others: List[Symbol] = members - var symtpe: Type = null - while ((others ne null) && { - val other = others.head - (other ne sym) && - ((other.owner eq sym.owner) || + def findMemberInternal: Symbol = { + var member: Symbol = NoSymbol + var members: List[Symbol] = null + var lastM: ::[Symbol] = null + if (Statistics.canEnable) Statistics.incCounter(findMemberCount) + val start = if (Statistics.canEnable) Statistics.pushTimer(typeOpsStack, findMemberNanos) else null + + //Console.println("find member " + name.decode + " in " + this + ":" + this.baseClasses)//DEBUG + var membertpe: Type = null + var required = requiredFlags + var excluded = excludedFlags | DEFERRED + var continue = true + var self: Type = null + + while (continue) { + continue = false + val bcs0 = baseClasses + var bcs = bcs0 + while (!bcs.isEmpty) { + val decls = bcs.head.info.decls + var entry = decls.lookupEntry(name) + while (entry ne null) { + val sym = entry.sym + val flags = sym.flags + if ((flags & required) == required) { + val excl = flags & excluded + if (excl == 0L && + (// omit PRIVATE LOCALS unless selector class is contained in class owning the def. + (bcs eq bcs0) || + (flags & PrivateLocal) != PrivateLocal || + (bcs0.head.hasTransOwner(bcs.head)))) { + if (name.isTypeName || stableOnly && sym.isStable) { + if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) + return sym + } else if (member eq NoSymbol) { + member = sym + } else if (members eq null) { + if ((member ne sym) && + ((member.owner eq sym.owner) || (flags & PRIVATE) != 0 || { if (self eq null) self = this.narrow - if (symtpe eq null) symtpe = self.memberType(sym) - !(self.memberType(other) matches symtpe) - })}) { - others = others.tail - } - if (others eq null) { - val lastM1 = new ::(sym, null) - lastM.tl = lastM1 - lastM = lastM1 + if (membertpe eq null) membertpe = self.memberType(member) + !(membertpe matches self.memberType(sym)) + })) { + lastM = new ::(sym, null) + members = member :: lastM + } + } else { + var others: List[Symbol] = members + var symtpe: Type = null + while ((others ne null) && { + val other = others.head + (other ne sym) && + ((other.owner eq sym.owner) || + (flags & PRIVATE) != 0 || { + if (self eq null) self = this.narrow + if (symtpe eq null) symtpe = self.memberType(sym) + !(self.memberType(other) matches symtpe) + })}) { + others = others.tail + } + if (others eq null) { + val lastM1 = new ::(sym, null) + lastM.tl = lastM1 + lastM = lastM1 + } } + } else if (excl == DEFERRED) { + continue = true } - } else if (excl == DEFERRED) { - continue = true } - } - entry = decls lookupNextEntry entry - } // while (entry ne null) - // excluded = excluded | LOCAL - bcs = if (name == nme.CONSTRUCTOR) Nil else bcs.tail - } // while (!bcs.isEmpty) - required |= DEFERRED - excluded &= ~(DEFERRED.toLong) - } // while (continue) - if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) - if (suspension ne null) suspension foreach (_.suspended = false) - if (members eq null) { - if (member == NoSymbol) if (Statistics.canEnable) Statistics.incCounter(noMemberCount) - member - } else { - if (Statistics.canEnable) Statistics.incCounter(multMemberCount) - lastM.tl = Nil - baseClasses.head.newOverloaded(this, members) + entry = decls lookupNextEntry entry + } // while (entry ne null) + // excluded = excluded | LOCAL + bcs = if (name == nme.CONSTRUCTOR) Nil else bcs.tail + } // while (!bcs.isEmpty) + required |= DEFERRED + excluded &= ~(DEFERRED.toLong) + } // while (continue) + if (Statistics.canEnable) Statistics.popTimer(typeOpsStack, start) + if (members eq null) { + if (member == NoSymbol) if (Statistics.canEnable) Statistics.incCounter(noMemberCount) + member + } else { + if (Statistics.canEnable) Statistics.incCounter(multMemberCount) + lastM.tl = Nil + baseClasses.head.newOverloaded(this, members) + } } + + if (this.isGround) findMemberInternal + else suspendingTypeVars(typeVarsInType(this))(findMemberInternal) } /** The (existential or otherwise) skolems and existentially quantified variables which are free in this type */ @@ -3072,7 +3065,10 @@ trait Types extends api.Types { self: SymbolTable => // invariant: before mutating constr, save old state in undoLog // (undoLog is used to reset constraints to avoid piling up unrelated ones) def setInst(tp: Type) { -// assert(!(tp containsTp this), this) + if (tp eq this) { + log(s"TypeVar cycle: called setInst passing $this to itself.") + return + } undoLog record this // if we were compared against later typeskolems, repack the existential, // because skolems are only compatible if they were created at the same level @@ -3217,16 +3213,19 @@ trait Types extends api.Types { self: SymbolTable => def registerTypeEquality(tp: Type, typeVarLHS: Boolean): Boolean = { // println("regTypeEq: "+(safeToString, debugString(tp), tp.getClass, if (typeVarLHS) "in LHS" else "in RHS", if (suspended) "ZZ" else if (constr.instValid) "IV" else "")) //@MDEBUG -// println("constr: "+ constr) - def checkIsSameType(tp: Type) = - if(typeVarLHS) constr.inst =:= tp - else tp =:= constr.inst + def checkIsSameType(tp: Type) = ( + if (typeVarLHS) constr.inst =:= tp + else tp =:= constr.inst + ) if (suspended) tp =:= origin else if (constr.instValid) checkIsSameType(tp) else isRelatable(tp) && { val newInst = wildcardToTypeVarMap(tp) - (constr isWithinBounds newInst) && { setInst(tp); true } + (constr isWithinBounds newInst) && { + setInst(newInst) + true + } } } @@ -5034,28 +5033,18 @@ trait Types extends api.Types { self: SymbolTable => class SubTypePair(val tp1: Type, val tp2: Type) { override def hashCode = tp1.hashCode * 41 + tp2.hashCode - override def equals(other: Any) = other match { + override def equals(other: Any) = (this eq other.asInstanceOf[AnyRef]) || (other match { + // suspend TypeVars in types compared by =:=, + // since we don't want to mutate them simply to check whether a subtype test is pending + // in addition to making subtyping "more correct" for type vars, + // it should avoid the stackoverflow that's been plaguing us (https://groups.google.com/d/topic/scala-internals/2gHzNjtB4xA/discussion) + // this method is only called when subtyping hits a recursion threshold (subsametypeRecursions >= LogPendingSubTypesThreshold) case stp: SubTypePair => - // suspend TypeVars in types compared by =:=, - // since we don't want to mutate them simply to check whether a subtype test is pending - // in addition to making subtyping "more correct" for type vars, - // it should avoid the stackoverflow that's been plaguing us (https://groups.google.com/d/topic/scala-internals/2gHzNjtB4xA/discussion) - // this method is only called when subtyping hits a recursion threshold (subsametypeRecursions >= LogPendingSubTypesThreshold) - def suspend(tp: Type) = - if (tp.isGround) null else suspendTypeVarsInType(tp) - def revive(suspension: List[TypeVar]) = - if (suspension ne null) suspension foreach (_.suspended = false) - - val suspensions = Array(tp1, stp.tp1, tp2, stp.tp2) map suspend - - val sameTypes = (tp1 =:= stp.tp1) && (tp2 =:= stp.tp2) - - suspensions foreach revive - - sameTypes + val tvars = List(tp1, stp.tp1, tp2, stp.tp2) flatMap (t => if (t.isGround) Nil else typeVarsInType(t)) + suspendingTypeVars(tvars)(tp1 =:= stp.tp1 && tp2 =:= stp.tp2) case _ => false - } + }) override def toString = tp1+" <:<? "+tp2 } @@ -5127,32 +5116,33 @@ trait Types extends api.Types { self: SymbolTable => def isPopulated(tp1: Type, tp2: Type): Boolean = { def isConsistent(tp1: Type, tp2: Type): Boolean = (tp1, tp2) match { case (TypeRef(pre1, sym1, args1), TypeRef(pre2, sym2, args2)) => - assert(sym1 == sym2) + assert(sym1 == sym2, (sym1, sym2)) pre1 =:= pre2 && - forall3(args1, args2, sym1.typeParams) { (arg1, arg2, tparam) => - //if (tparam.variance == 0 && !(arg1 =:= arg2)) Console.println("inconsistent: "+arg1+"!="+arg2)//DEBUG + forall3(args1, args2, sym1.typeParams)((arg1, arg2, tparam) => if (tparam.variance == 0) arg1 =:= arg2 - else if (arg1.isInstanceOf[TypeVar]) - // if left-hand argument is a typevar, make it compatible with variance - // this is for more precise pattern matching - // todo: work this in the spec of this method - // also: think what happens if there are embedded typevars? - if (tparam.variance < 0) arg1 <:< arg2 else arg2 <:< arg1 - else true - } + // if left-hand argument is a typevar, make it compatible with variance + // this is for more precise pattern matching + // todo: work this in the spec of this method + // also: think what happens if there are embedded typevars? + else arg1 match { + case _: TypeVar => if (tparam.variance < 0) arg1 <:< arg2 else arg2 <:< arg1 + case _ => true + } + ) case (et: ExistentialType, _) => et.withTypeVars(isConsistent(_, tp2)) case (_, et: ExistentialType) => et.withTypeVars(isConsistent(tp1, _)) } - def check(tp1: Type, tp2: Type) = + def check(tp1: Type, tp2: Type) = ( if (tp1.typeSymbol.isClass && tp1.typeSymbol.hasFlag(FINAL)) tp1 <:< tp2 || isNumericValueClass(tp1.typeSymbol) && isNumericValueClass(tp2.typeSymbol) else tp1.baseClasses forall (bc => tp2.baseTypeIndex(bc) < 0 || isConsistent(tp1.baseType(bc), tp2.baseType(bc))) + ) - check(tp1, tp2)/* && check(tp2, tp1)*/ // need to investgate why this can't be made symmetric -- neg/gadts1 fails, and run/existials also. + check(tp1, tp2) && check(tp2, tp1) } /** Does a pattern of type `patType` need an outer test when executed against @@ -5235,13 +5225,15 @@ trait Types extends api.Types { self: SymbolTable => try { val before = undoLog.log var result = false - - try result = { - isSameType1(tp1, tp2) - } finally if (!result) undoLog.undoTo(before) + try { + result = isSameType1(tp1, tp2) + } + finally if (!result) undoLog.undoTo(before) result - } finally undoLog.unlock() - } finally { + } + finally undoLog.unlock() + } + finally { subsametypeRecursions -= 1 // 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) // it doesn't help to keep separate recursion counts for the three methods that now share it @@ -5523,12 +5515,12 @@ trait Types extends api.Types { self: SymbolTable => } tp1 match { case tv @ TypeVar(_,_) => - return tv.registerTypeEquality(tp2, true) + return tv.registerTypeEquality(tp2, typeVarLHS = true) case _ => } tp2 match { case tv @ TypeVar(_,_) => - return tv.registerTypeEquality(tp1, false) + return tv.registerTypeEquality(tp1, typeVarLHS = false) case _ => } tp1 match { @@ -6803,15 +6795,22 @@ trait Types extends api.Types { self: SymbolTable => } tvs.reverse } - /** Make each type var in this type use its original type for comparisons instead - * of collecting constraints. - */ - def suspendTypeVarsInType(tp: Type): List[TypeVar] = { - val tvs = typeVarsInType(tp) - // !!! Is it somehow guaranteed that this will not break under nesting? - // In general one has to save and restore the contents of the field... + + // If this type contains type variables, put them to sleep for a while. + // Don't just wipe them out by replacing them by the corresponding type + // parameter, as that messes up (e.g.) type variables in type refinements. + // Without this, the matchesType call would lead to type variables on both + // sides of a subtyping/equality judgement, which can lead to recursive types + // being constructed. See pos/t0851 for a situation where this happens. + def suspendingTypeVarsInType[T](tp: Type)(op: => T): T = + suspendingTypeVars(typeVarsInType(tp))(op) + + @inline final def suspendingTypeVars[T](tvs: List[TypeVar])(op: => T): T = { + val saved = tvs map (_.suspended) tvs foreach (_.suspended = true) - tvs + + try op + finally foreach2(tvs, saved)(_.suspended = _) } /** Compute lub (if `variance == 1`) or glb (if `variance == -1`) of given list |