From 9e2b10fc02a60a8e24c38a8f0e52b5196c47145f Mon Sep 17 00:00:00 2001 From: Miles Sabin Date: Fri, 20 May 2016 12:49:25 +0100 Subject: SI-2712 Add support for higher order unification --- .../scala/tools/nsc/settings/ScalaSettings.scala | 1 + src/reflect/scala/reflect/internal/Types.scala | 40 +++++++++++++++++++--- .../internal/settings/MutableSettings.scala | 1 + src/reflect/scala/reflect/runtime/Settings.scala | 1 + 4 files changed, 38 insertions(+), 5 deletions(-) (limited to 'src') diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala index 1817cfa25a..8e5c064e1f 100644 --- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala +++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala @@ -218,6 +218,7 @@ trait ScalaSettings extends AbsScalaSettings val inferByName = BooleanSetting ("-Yinfer-by-name", "Allow inference of by-name types. This is a temporary option to ease transition. See SI-7899.").withDeprecationMessage(removalIn212) val YclasspathImpl = ChoiceSetting ("-YclasspathImpl", "implementation", "Choose classpath scanning method.", List(ClassPathRepresentationType.Recursive, ClassPathRepresentationType.Flat), ClassPathRepresentationType.Recursive) val YdisableFlatCpCaching = BooleanSetting ("-YdisableFlatCpCaching", "Do not cache flat classpath representation of classpath elements from jars across compiler instances.") + val YpartialUnification = BooleanSetting ("-Ypartial-unification", "Enable partial unification in type constructor inference") val YvirtClasses = false // too embryonic to even expose as a -Y //BooleanSetting ("-Yvirtual-classes", "Support virtual classes") val YdisableUnreachablePrevention = BooleanSetting("-Ydisable-unreachable-prevention", "Disable the prevention of unreachable blocks in code generation.") diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala index 9697e16da7..98510825c0 100644 --- a/src/reflect/scala/reflect/internal/Types.scala +++ b/src/reflect/scala/reflect/internal/Types.scala @@ -3076,13 +3076,43 @@ trait Types */ def unifyFull(tpe: Type): Boolean = { def unifySpecific(tp: Type) = { - sameLength(typeArgs, tp.typeArgs) && { - val lhs = if (isLowerBound) tp.typeArgs else typeArgs - val rhs = if (isLowerBound) typeArgs else tp.typeArgs + val tpTypeArgs = tp.typeArgs + val arityDelta = compareLengths(typeArgs, tpTypeArgs) + if (arityDelta == 0) { + val lhs = if (isLowerBound) tpTypeArgs else typeArgs + val rhs = if (isLowerBound) typeArgs else tpTypeArgs // This is a higher-kinded type var with same arity as tp. // If so (see SI-7517), side effect: adds the type constructor itself as a bound. - isSubArgs(lhs, rhs, params, AnyDepth) && { addBound(tp.typeConstructor); true } - } + isSubArgs(lhs, rhs, params, AnyDepth) && {addBound(tp.typeConstructor); true} + } else if (settings.YpartialUnification && arityDelta < 0 && typeArgs.nonEmpty) { + // Simple algorithm as suggested by Paul Chiusano in the comments on SI-2712 + // + // https://issues.scala-lang.org/browse/SI-2712?focusedCommentId=61270 + // + // Treat the type constructor as curried and partially applied, we treat a prefix + // as constants and solve for the suffix. For the example in the ticket, unifying + // M[A] with Int => Int this unifies as, + // + // M[t] = [t][Int => t] --> abstract on the right to match the expected arity + // A = Int --> capture the remainder on the left + // + // A more "natural" unifier might be M[t] = [t][t => t]. There's lots of scope for + // experimenting with alternatives here. + val numCaptured = tpTypeArgs.length - typeArgs.length + val (captured, abstractedArgs) = tpTypeArgs.splitAt(numCaptured) + + val (lhs, rhs) = + if (isLowerBound) (abstractedArgs, typeArgs) + else (typeArgs, abstractedArgs) + + isSubArgs(lhs, rhs, params, AnyDepth) && { + val tpSym = tp.typeSymbolDirect + val abstractedTypeParams = tpSym.typeParams.drop(numCaptured).map(_.cloneSymbol(tpSym)) + + addBound(PolyType(abstractedTypeParams, appliedType(tp.typeConstructor, captured ++ abstractedTypeParams.map(_.tpeHK)))) + true + } + } else false } // The type with which we can successfully unify can be hidden // behind singleton types and type aliases. diff --git a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala index 38893d8db3..3de720da11 100644 --- a/src/reflect/scala/reflect/internal/settings/MutableSettings.scala +++ b/src/reflect/scala/reflect/internal/settings/MutableSettings.scala @@ -53,6 +53,7 @@ abstract class MutableSettings extends AbsSettings { def printtypes: BooleanSetting def uniqid: BooleanSetting def verbose: BooleanSetting + def YpartialUnification: BooleanSetting def Yrecursion: IntSetting def maxClassfileName: IntSetting diff --git a/src/reflect/scala/reflect/runtime/Settings.scala b/src/reflect/scala/reflect/runtime/Settings.scala index 27d574b1de..1081218a70 100644 --- a/src/reflect/scala/reflect/runtime/Settings.scala +++ b/src/reflect/scala/reflect/runtime/Settings.scala @@ -47,6 +47,7 @@ private[reflect] class Settings extends MutableSettings { val printtypes = new BooleanSetting(false) val uniqid = new BooleanSetting(false) val verbose = new BooleanSetting(false) + val YpartialUnification = new BooleanSetting(false) val Yrecursion = new IntSetting(0) val maxClassfileName = new IntSetting(255) -- cgit v1.2.3