diff options
author | Jason Zaugg <jzaugg@gmail.com> | 2014-01-14 13:37:26 +0100 |
---|---|---|
committer | Jason Zaugg <jzaugg@gmail.com> | 2014-01-14 16:00:29 +0100 |
commit | a09e143b7fd1c6b433386d45e9c5ae3548819b59 (patch) | |
tree | 09ab06f0c5532588f6cf96bc132e751f116eea5b /src | |
parent | 2e28cf7f76c3d5fd0c2df4274f1af9acb42de699 (diff) | |
download | scala-a09e143b7fd1c6b433386d45e9c5ae3548819b59.tar.gz scala-a09e143b7fd1c6b433386d45e9c5ae3548819b59.tar.bz2 scala-a09e143b7fd1c6b433386d45e9c5ae3548819b59.zip |
SI-8146 Fix non-deterministic <:< for deeply nested types
In the interests of keeping subtyping decidable [1], 152563b
added some bookkeeping to `isSubType` to detect cycles.
However, this was based on a hash set containing instances of
`SubTypePair`, and that class had inconsistencies between its
`hashCode` (in terms of `Type#hashCode`) and `equals`
(in terms of `=:=`).
This inconsistency can be seen in:
scala> trait C { def apply: (Int @unchecked) }
defined trait C
scala> val intUnchecked = typeOf[C].decls.head.info.finalResultType
intUnchecked: $r.intp.global.Type = Int @unchecked
scala> val p1 = new SubTypePair(intUnchecked, intUnchecked)
p1: $r.intp.global.SubTypePair = Int @unchecked <:<? Int @unchecked
scala> val p2 = new SubTypePair(intUnchecked.withoutAnnotations, intUnchecked.withoutAnnotations)
p2: $r.intp.global.SubTypePair = Int <:<? Int
scala> p1 == p2
res0: Boolean = true
scala> p1.hashCode == p2.hashCode
res1: Boolean = false
This commit switches to using `Type#==`, by way of the standard
case class equality.
The risk here is that you could find a subtyping computation that
progresses in such a manner that we don't detect the cycle. It would
need to produce an infinite stream of representations for types that
were `=:=` but not `==`. If that happened, we'd fail to terminate,
rather than judging the relationship as `false`.
[1] http://research.microsoft.com/pubs/64041/fool2007.pdf
Diffstat (limited to 'src')
-rw-r--r-- | src/reflect/scala/reflect/internal/tpe/TypeComparers.scala | 25 | ||||
-rw-r--r-- | src/reflect/scala/reflect/runtime/JavaUniverseForce.scala | 1 |
2 files changed, 11 insertions, 15 deletions
diff --git a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala index b60fecd66e..027da6ed50 100644 --- a/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala +++ b/src/reflect/scala/reflect/internal/tpe/TypeComparers.scala @@ -17,20 +17,15 @@ trait TypeComparers { private val _pendingSubTypes = new mutable.HashSet[SubTypePair] def pendingSubTypes = _pendingSubTypes - class SubTypePair(val tp1: Type, val tp2: Type) { - override def hashCode = tp1.hashCode * 41 + tp2.hashCode - 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 => - 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 - }) + final case class SubTypePair(tp1: Type, tp2: Type) { + // SI-8146 we used to implement equality here in terms of pairwise =:=. + // But, this was inconsistent with hashCode, which was based on the + // Type#hashCode, based on the structure of types, not the meaning. + // Now, we use `Type#{equals,hashCode}` as the (consistent) basis for + // detecting cycles (aka keeping subtyping decidable.) + // + // I added a tests to show that we detect the cycle: neg/t8146-no-finitary* + override def toString = tp1+" <:<? "+tp2 } @@ -262,7 +257,7 @@ trait TypeComparers { if (subsametypeRecursions >= LogPendingSubTypesThreshold) { val p = new SubTypePair(tp1, tp2) if (pendingSubTypes(p)) - false + false // see neg/t8146-no-finitary* else try { pendingSubTypes += p diff --git a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala index c87995275f..a2d3206156 100644 --- a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala +++ b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala @@ -198,6 +198,7 @@ trait JavaUniverseForce { self: runtime.JavaUniverse => this.ErroneousCollector this.adaptToNewRunMap // inaccessible: this.commonOwnerMapObj + this.SubTypePair this.SymbolKind this.NoSymbol this.CyclicReference |