From dfe0ba847e8751896948522df5a24e13754b43bf Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Tue, 19 Nov 2013 20:03:48 +0100 Subject: SI-7983 Fix regression in implicit divergence checking As seen in Slick. Regressed in 039b1cb1a5b8. In that commit, a call to `normalize` was replaced with `dealiasWiden` as part of a broad sweeping change. However, while the latter does less than the former with regards to eta expansion ofhigher kinded type refs (the motivation of that commit), it also does more when it comes to singleton types: they are widened to the underlying type. This was widening away `SingleType(<>, <>)` before the special case assiging that type component a complexity of zero could kick in. In the test case, extracted from Slick, this meant that the divergence check would consider that the second type below to outrank the first in the complexity measure, and abort the implicit search. Shape[?, ? (Coffees, Coffees), ?] Shape[DivergenceTest.this.Flat, ?, Coffees, ?] After this change, the number of packages enclosing `DivergenceTest` no longer has a bearing on the complexity score of the type. Here's how the race was run before hand: complexity(): 0 complexity(): 1 complexity(foo.type): 2 complexity(foo.bar.type): 3 complexity(foo.bar.baz.type): 4 complexity(DivergenceTest.this.type): 5 complexity(): 0 complexity(): 1 complexity(foo.type): 2 complexity(foo.bar.type): 3 complexity(foo.bar.baz.type): 4 complexity(DivergenceTest.this.type): 5 complexity(DivergenceTest.this.Flat): 6 complexity(): 0 complexity(): 1 complexity(scala.type): 2 complexity(Int): 3 complexity(?): 1 complexity(DivergenceTest.this.Shape2[DivergenceTest.this.Flat,Int,?]): 16 complexity(): 0 complexity(): 1 complexity(foo.type): 2 complexity(foo.bar.type): 3 complexity(foo.bar.baz.type): 4 complexity(DivergenceTest.this.type): 5 complexity(?): 1 complexity(): 0 complexity(): 1 complexity(scala.type): 2 complexity(): 0 complexity(Coffees): 1 complexity(): 0 complexity(): 1 complexity(scala.type): 2 complexity(Int): 3 complexity((Coffees, Int)): 7 complexity(?): 1 complexity(DivergenceTest.this.Shape2[?,(Coffees, Int),?]): 15 dominates(DivergenceTest.this.Shape2[_ <: DivergenceTest.this.Flat, Int, U2], DivergenceTest.this.Shape2[_ <: Level, (Coffees, Int), U1]): true And afterwards: complexity(DivergenceTest.this.type): 1 complexity(DivergenceTest.this.type): 1 complexity(DivergenceTest.this.Flat): 2 complexity(scala.type): 1 complexity(Int): 2 complexity(?): 1 complexity(DivergenceTest.this.Shape2[DivergenceTest.this.Flat,Int,?]): 7 complexity(DivergenceTest.this.type): 1 complexity(?): 1 complexity(scala.type): 1 complexity(): 0 complexity(Coffees): 1 complexity(scala.type): 1 complexity(Int): 2 complexity((Coffees, Int)): 5 complexity(?): 1 complexity(DivergenceTest.this.Shape2[?,(Coffees, Int),?]): 9 dominates(DivergenceTest.this.Shape2[_ <: DivergenceTest.this.Flat, Int, U2], DivergenceTest.this.Shape2[_ <: Level, (Coffees, Int), U1]): false Notice that even in the after shot, `scala.Int` has a complexity of 2. It should be 1; this will be fixed in a separate commit. --- src/compiler/scala/tools/nsc/typechecker/Implicits.scala | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/compiler') diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala index 01acbb8cc2..c3891dc707 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala @@ -402,7 +402,7 @@ trait Implicits { deriveTypeWithWildcards(syms.distinct)(tp) } def sum(xs: List[Int]) = (0 /: xs)(_ + _) - def complexity(tp: Type): Int = tp.dealiasWiden match { + def complexity(tp: Type): Int = tp.dealias match { case NoPrefix => 0 case SingleType(pre, sym) => -- cgit v1.2.3 From d8ffaac6ae544457fa43f2ede674bbe80930cc27 Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Tue, 19 Nov 2013 20:23:40 +0100 Subject: Code reformatting in Implicits And use List#sum, rather than a fold. No functional change. --- .../scala/tools/nsc/typechecker/Implicits.scala | 26 +++++++++------------- 1 file changed, 10 insertions(+), 16 deletions(-) (limited to 'src/compiler') diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala index c3891dc707..d9a4f60d48 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala @@ -388,11 +388,11 @@ trait Implicits { */ private def dominates(dtor: Type, dted: Type): Boolean = { def core(tp: Type): Type = tp.dealiasWiden match { - case RefinedType(parents, defs) => intersectionType(parents map core, tp.typeSymbol.owner) + case RefinedType(parents, defs) => intersectionType(parents map core, tp.typeSymbol.owner) case AnnotatedType(annots, tp, selfsym) => core(tp) - case ExistentialType(tparams, result) => core(result).subst(tparams, tparams map (t => core(t.info.bounds.hi))) - case PolyType(tparams, result) => core(result).subst(tparams, tparams map (t => core(t.info.bounds.hi))) - case _ => tp + case ExistentialType(tparams, result) => core(result).subst(tparams, tparams map (t => core(t.info.bounds.hi))) + case PolyType(tparams, result) => core(result).subst(tparams, tparams map (t => core(t.info.bounds.hi))) + case _ => tp } def stripped(tp: Type): Type = { // `t.typeSymbol` returns the symbol of the normalized type. If that normalized type @@ -401,23 +401,17 @@ trait Implicits { val syms = for (t <- tp; if t.typeSymbol.isTypeParameter) yield t.typeSymbol deriveTypeWithWildcards(syms.distinct)(tp) } - def sum(xs: List[Int]) = (0 /: xs)(_ + _) def complexity(tp: Type): Int = tp.dealias match { - case NoPrefix => - 0 - case SingleType(pre, sym) => - if (sym.isPackage) 0 else complexity(tp.dealiasWiden) - case TypeRef(pre, sym, args) => - complexity(pre) + sum(args map complexity) + 1 - case RefinedType(parents, _) => - sum(parents map complexity) + 1 - case _ => - 1 + case NoPrefix => 0 + case SingleType(pre, sym) => if (sym.isPackage) 0 else complexity(tp.dealiasWiden) + case TypeRef(pre, sym, args) => complexity(pre) + (args map complexity).sum + 1 + case RefinedType(parents, _) => (parents map complexity).sum + 1 + case _ => 1 } def overlaps(tp1: Type, tp2: Type): Boolean = (tp1, tp2) match { case (RefinedType(parents, _), _) => parents exists (overlaps(_, tp2)) case (_, RefinedType(parents, _)) => parents exists (overlaps(tp1, _)) - case _ => tp1.typeSymbol == tp2.typeSymbol + case _ => tp1.typeSymbol == tp2.typeSymbol } val dtor1 = stripped(core(dtor)) val dted1 = stripped(core(dted)) -- cgit v1.2.3 From 60ac821192c1b19f91f19eb7a746f0889b3e804e Mon Sep 17 00:00:00 2001 From: Jason Zaugg Date: Tue, 19 Nov 2013 20:33:43 +0100 Subject: Account for a variation of package types in Implicit Divergence. While debugging pos/t7983.scala, I noticed that: complexity(scala.type): 1 complexity(Int): 2 The intent of the code is that top level classes should have a complexity of one. This commit restores that for cases when we see the prefix type as a ThisType, rather than a SingleType. I can't construct a test case in which this small difference is observable in the divergence checks. --- src/compiler/scala/tools/nsc/typechecker/Implicits.scala | 1 + 1 file changed, 1 insertion(+) (limited to 'src/compiler') diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala index d9a4f60d48..025c262c8d 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala @@ -404,6 +404,7 @@ trait Implicits { def complexity(tp: Type): Int = tp.dealias match { case NoPrefix => 0 case SingleType(pre, sym) => if (sym.isPackage) 0 else complexity(tp.dealiasWiden) + case ThisType(sym) => if (sym.isPackage) 0 else 1 case TypeRef(pre, sym, args) => complexity(pre) + (args map complexity).sum + 1 case RefinedType(parents, _) => (parents map complexity).sum + 1 case _ => 1 -- cgit v1.2.3