Merge pull request #3859 from xeno-by/topic/fundep-materialization-210x

[backport] SI-7470 implements fundep materialization

19 files changed, 215 insertions, 4 deletions

diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
index dbfaa2c531..56fc4d7594 100644
--- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
+++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala
@@ -179,6 +179,7 @@ trait ScalaSettings extends AbsScalaSettings
   val YvirtClasses    = false // too embryonic to even expose as a -Y //BooleanSetting    ("-Yvirtual-classes", "Support virtual classes")
 
   val exposeEmptyPackage = BooleanSetting("-Yexpose-empty-package", "Internal only: expose the empty package.").internalOnly()
+  val YfundepMaterialization = BooleanSetting("-Yfundep-materialization", "Turn on the 2.11 behavior of macro expansion being able to influence type inference in implicit searches")
 
   def stop = stopAfter
 
diff --git a/src/compiler/scala/tools/nsc/typechecker/Macros.scala b/src/compiler/scala/tools/nsc/typechecker/Macros.scala
index d6ec5f2cb0..c0844ec8fc 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Macros.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Macros.scala
@@ -713,6 +713,13 @@ trait Macros extends scala.tools.reflect.FastTrack with Traces {
 
             var expectedTpe = expandee.tpe
             if (isNullaryInvocation(expandee)) expectedTpe = expectedTpe.finalResultType
+            if (settings.YfundepMaterialization.value) {
+              // approximation is necessary for whitebox macros to guide type inference
+              // read more in the comments for onDelayed below
+              val undetparams = expectedTpe collect { case tp if tp.typeSymbol.isTypeParameter => tp.typeSymbol }
+              expectedTpe = deriveTypeWithWildcards(undetparams)(expectedTpe)
+            }
+
             // also see http://groups.google.com/group/scala-internals/browse_thread/thread/492560d941b315cc
             val expanded0 = duplicateAndKeepPositions(expanded)
             val expanded1 = typecheck("macro def return type", expanded0, expectedTpe)
@@ -766,9 +773,24 @@ trait Macros extends scala.tools.reflect.FastTrack with Traces {
           // (in a sense that a datatype's uniform representation is unambiguously determined by the datatype,
           // e.g. for Foo it will be Int :: String :: Boolean :: HNil), there's no way to convey this information
           // to the typechecker. Therefore the typechecker will infer Nothing for L, which is hardly what we want.
+          //
+          // =========== THE SOLUTION ===========
+          //
+          // To give materializers a chance to say their word before vanilla inference kicks in,
+          // we infer as much as possible (e.g. in the example above even though L is hopeless, C still can be inferred to Foo)
+          // and then trigger macro expansion with the undetermined type parameters still there.
+          // Thanks to that the materializer can take a look at what's going on and react accordingly.
+          //
+          // NOTE: This functionality is only available under the -Xfundep-materialization flag in Scala 2.10,
+          // but is enabled by default in Scala 2.11.
           val shouldInstantiate = typer.context.undetparams.nonEmpty && !inPolyMode(mode)
-          if (shouldInstantiate) typer.instantiatePossiblyExpectingUnit(delayed, mode, pt)
-          else delayed
+          if (shouldInstantiate) {
+            if (settings.YfundepMaterialization.value) {
+              forced += delayed
+              typer.infer.inferExprInstance(delayed, typer.context.extractUndetparams(), pt, keepNothings = false)
+              macroExpand(typer, delayed, mode, pt)
+            } else typer.instantiatePossiblyExpectingUnit(delayed, mode, pt)
+          } else delayed
         case Fallback(fallback) =>
           typer.context.withImplicitsEnabled(typer.typed(fallback, EXPRmode, pt))
         case Other(result) =>
@@ -886,10 +908,13 @@ trait Macros extends scala.tools.reflect.FastTrack with Traces {
    *    2) undetparams (sym.isTypeParameter && !sym.isSkolem)
    */
   var hasPendingMacroExpansions = false
+  private val forced = perRunCaches.newWeakSet[Tree]
   private val delayed = perRunCaches.newWeakMap[Tree, scala.collection.mutable.Set[Int]]
   private def isDelayed(expandee: Tree) = delayed contains expandee
   private def calculateUndetparams(expandee: Tree): scala.collection.mutable.Set[Int] =
-    delayed.get(expandee).getOrElse {
+    // !settings.YfundepMaterialization.value implies forced.isEmpty
+    if (forced(expandee)) scala.collection.mutable.Set[Int]()
+    else delayed.getOrElse(expandee, {
       val calculated = scala.collection.mutable.Set[Symbol]()
       expandee foreach (sub => {
         def traverse(sym: Symbol) = if (sym != null && (undetparams contains sym.id)) calculated += sym
@@ -898,7 +923,7 @@ trait Macros extends scala.tools.reflect.FastTrack with Traces {
       })
       macroLogVerbose("calculateUndetparams: %s".format(calculated))
       calculated map (_.id)
-    }
+    })
   private val undetparams = perRunCaches.newSet[Int]
   def notifyUndetparamsAdded(newUndets: List[Symbol]): Unit = {
     undetparams ++= newUndets map (_.id)
diff --git a/test/files/neg/t5923c.check b/test/files/neg/t5923c.check
new file mode 100644
index 0000000000..6d3d6b1b78
--- /dev/null
+++ b/test/files/neg/t5923c.check
@@ -0,0 +1,4 @@
+Test_2.scala:7: error: could not find implicit value for parameter iso: Iso[Test.Foo,L]
+    val equiv = foo(Foo(23, "foo", true))
+                   ^
+one error found
diff --git a/test/files/neg/t5923c/Macros_1.scala b/test/files/neg/t5923c/Macros_1.scala
new file mode 100644
index 0000000000..0b7a3399e2
--- /dev/null
+++ b/test/files/neg/t5923c/Macros_1.scala
@@ -0,0 +1,39 @@
+import language.experimental.macros
+import scala.reflect.macros.Context
+
+trait Iso[T, U] {
+  def to(t : T) : U
+  // def from(u : U) : T
+}
+
+object Iso {
+  implicit def materializeIso[T, U]: Iso[T, U] = macro impl[T, U]
+  def impl[T: c.WeakTypeTag, U: c.WeakTypeTag](c: Context): c.Expr[Iso[T, U]] = {
+    import c.universe._
+    import definitions._
+    import Flag._
+
+    val sym = c.weakTypeOf[T].typeSymbol
+    if (!sym.isClass || !sym.asClass.isCaseClass) c.abort(c.enclosingPosition, s"$sym is not a case class")
+    val fields = sym.typeSignature.declarations.toList.collect{ case x: TermSymbol if x.isVal && x.isCaseAccessor => x }
+
+    def mkTpt() = {
+      val core = Ident(TupleClass(fields.length) orElse UnitClass)
+      if (fields.length == 0) core
+      else AppliedTypeTree(core, fields map (f => TypeTree(f.typeSignature)))
+    }
+
+    def mkFrom() = {
+      if (fields.length == 0) Literal(Constant(Unit))
+      else Apply(Ident(newTermName("Tuple" + fields.length)), fields map (f => Select(Ident(newTermName("f")), newTermName(f.name.toString.trim))))
+    }
+
+    val evidenceClass = ClassDef(Modifiers(FINAL), newTypeName("$anon"), List(), Template(
+      List(AppliedTypeTree(Ident(newTypeName("Iso")), List(Ident(sym), mkTpt()))),
+      emptyValDef,
+      List(
+        DefDef(Modifiers(), nme.CONSTRUCTOR, List(), List(List()), TypeTree(), Block(List(Apply(Select(Super(This(tpnme.EMPTY), tpnme.EMPTY), nme.CONSTRUCTOR), List())), Literal(Constant(())))),
+        DefDef(Modifiers(), newTermName("to"), List(), List(List(ValDef(Modifiers(PARAM), newTermName("f"), Ident(sym), EmptyTree))), TypeTree(), mkFrom()))))
+    c.Expr[Iso[T, U]](Block(List(evidenceClass), Apply(Select(New(Ident(newTypeName("$anon"))), nme.CONSTRUCTOR), List())))
+  }
+}
diff --git a/test/files/neg/t5923c/Test_2.scala b/test/files/neg/t5923c/Test_2.scala
new file mode 100644
index 0000000000..a00f4ed7db
--- /dev/null
+++ b/test/files/neg/t5923c/Test_2.scala
@@ -0,0 +1,12 @@
+// see the comments for macroExpandApply.onDelayed for an explanation of what's tested here
+object Test extends App {
+  case class Foo(i: Int, s: String, b: Boolean)
+  def foo[C, L](c: C)(implicit iso: Iso[C, L]): L = iso.to(c)
+
+  {
+    val equiv = foo(Foo(23, "foo", true))
+    def typed[T](t: => T) {}
+    typed[(Int, String, Boolean)](equiv)
+    println(equiv)
+  }
+}
\ No newline at end of file
diff --git a/test/files/run/t5923a.check b/test/files/run/t5923a-fundep.check
index 7165b734ac..7165b734ac 100644
--- a/test/files/run/t5923a.check
+++ b/test/files/run/t5923a-fundep.check
diff --git a/test/files/run/t5923a-fundep.flags b/test/files/run/t5923a-fundep.flags
new file mode 100644
index 0000000000..384b48d1b0
--- /dev/null
+++ b/test/files/run/t5923a-fundep.flags
@@ -0,0 +1 @@
+-Yfundep-materialization
\ No newline at end of file
diff --git a/test/files/run/t5923a-fundep/Macros_1.scala b/test/files/run/t5923a-fundep/Macros_1.scala
new file mode 100644
index 0000000000..97076eb102
--- /dev/null
+++ b/test/files/run/t5923a-fundep/Macros_1.scala
@@ -0,0 +1,52 @@
+import scala.reflect.macros.Context
+import language.experimental.macros
+
+case class C[T](t: String)
+object C {
+  implicit def foo[T]: C[T] = macro Macros.impl[T]
+}
+
+object Macros {
+  def impl[T](c: Context)(ttag: c.WeakTypeTag[T]) = {
+    import c.universe._
+    val ttag0 = ttag;
+    {
+      // When we're expanding implicitly[C[Nothing]], the type inferencer will see
+      // that foo[T] returns C[T] and that we request an implicit of type C[Nothing].
+      //
+      // Then the type inferencer will try to match C[T] against C[Nothing] and infer everything it can infer
+      // from that match, but not more (e.g. if we were returning Iso[T, U] and the type we were looking at was Iso[Foo, L],
+      // we wouldn't want U to be auto-inferred to Nothing, as it usually happens with normal methods,
+      // but would rather want it to remain unknown, so that our macro could take a stab at inferring it:
+      // see the comments in this commit for more information).
+      //
+      // Equipped with common sense, in our case of C[T] and C[Nothing] we would expect T to be inferred as Nothing, and then we
+      // would expect T in the corresponding macro invocation to be Nothing. Unfortunately it is not that simple.
+      //
+      // Internally the type inferencer uses Nothing as a dummy value, which stands for "don't know how to
+      // infer this type parameter". In the Iso example, matching Iso[T, U] against Iso[Foo, L] would result in
+      // T being inferred as Foo and U being inferred as Nothing (!!). Then the type inferencer will think:
+      // "Aha! U ended up being Nothing. This means that I failed to infer it,
+      // therefore the result of my work is: T -> Foo, U -> still unknown".
+      //
+      // That's all very good and works very well until Nothing is a genuine result of type inference,
+      // as in our original example of inferring T in C[T] from C[Nothing]. In that case, the inferencer becomes confused
+      // and here in the macro implementation we get weakTypeOf[T] equal to some dummy type carrying a type parameter
+      // instead of Nothing.
+      //
+      // This eccentric behavior of the type inferencer is a long-standing problem in scalac,
+      // so the best one can do for now until it's fixed is to work around, manually converting
+      // suspicious T's into Nothings. Of course, this means that we would have to approximate,
+      // because there's no way to know whether having T here stands for a failed attempt to infer Nothing
+      // or for a failed attempt to infer anything, but at least we're in full control of making the best
+      // of this sad situation.
+      implicit def ttag: WeakTypeTag[T] = {
+        val tpe = ttag0.tpe
+        val sym = tpe.typeSymbol.asType
+        if (sym.isParameter && !sym.isSkolem) TypeTag.Nothing.asInstanceOf[TypeTag[T]]
+        else ttag0
+      }
+      reify(C[T](c.literal(weakTypeOf[T].toString).splice))
+    }
+  }
+}
\ No newline at end of file
diff --git a/test/files/run/t5923a/Test_2.scala b/test/files/run/t5923a-fundep/Test_2.scala
index 001ff9aea8..001ff9aea8 100644
--- a/test/files/run/t5923a/Test_2.scala
+++ b/test/files/run/t5923a-fundep/Test_2.scala
diff --git a/test/files/run/t5923a-nofundep.check b/test/files/run/t5923a-nofundep.check
new file mode 100644
index 0000000000..7165b734ac
--- /dev/null
+++ b/test/files/run/t5923a-nofundep.check
@@ -0,0 +1,3 @@
+C(Int)
+C(String)
+C(Nothing)
diff --git a/test/files/run/t5923a/Macros_1.scala b/test/files/run/t5923a-nofundep/Macros_1.scala
index 6d21362c4d..6d21362c4d 100644
--- a/test/files/run/t5923a/Macros_1.scala
+++ b/test/files/run/t5923a-nofundep/Macros_1.scala
diff --git a/test/files/run/t5923a-nofundep/Test_2.scala b/test/files/run/t5923a-nofundep/Test_2.scala
new file mode 100644
index 0000000000..001ff9aea8
--- /dev/null
+++ b/test/files/run/t5923a-nofundep/Test_2.scala
@@ -0,0 +1,5 @@
+object Test extends App {
+  println(implicitly[C[Int]])
+  println(implicitly[C[String]])
+  println(implicitly[C[Nothing]])
+}
\ No newline at end of file
diff --git a/test/files/run/t5923c.check b/test/files/run/t5923c.check
new file mode 100644
index 0000000000..bed7429108
--- /dev/null
+++ b/test/files/run/t5923c.check
@@ -0,0 +1 @@
+(23,foo,true)
diff --git a/test/files/run/t5923c.flags b/test/files/run/t5923c.flags
new file mode 100644
index 0000000000..384b48d1b0
--- /dev/null
+++ b/test/files/run/t5923c.flags
@@ -0,0 +1 @@
+-Yfundep-materialization
\ No newline at end of file
diff --git a/test/files/run/t5923c/Macros_1.scala b/test/files/run/t5923c/Macros_1.scala
new file mode 100644
index 0000000000..0b7a3399e2
--- /dev/null
+++ b/test/files/run/t5923c/Macros_1.scala
@@ -0,0 +1,39 @@
+import language.experimental.macros
+import scala.reflect.macros.Context
+
+trait Iso[T, U] {
+  def to(t : T) : U
+  // def from(u : U) : T
+}
+
+object Iso {
+  implicit def materializeIso[T, U]: Iso[T, U] = macro impl[T, U]
+  def impl[T: c.WeakTypeTag, U: c.WeakTypeTag](c: Context): c.Expr[Iso[T, U]] = {
+    import c.universe._
+    import definitions._
+    import Flag._
+
+    val sym = c.weakTypeOf[T].typeSymbol
+    if (!sym.isClass || !sym.asClass.isCaseClass) c.abort(c.enclosingPosition, s"$sym is not a case class")
+    val fields = sym.typeSignature.declarations.toList.collect{ case x: TermSymbol if x.isVal && x.isCaseAccessor => x }
+
+    def mkTpt() = {
+      val core = Ident(TupleClass(fields.length) orElse UnitClass)
+      if (fields.length == 0) core
+      else AppliedTypeTree(core, fields map (f => TypeTree(f.typeSignature)))
+    }
+
+    def mkFrom() = {
+      if (fields.length == 0) Literal(Constant(Unit))
+      else Apply(Ident(newTermName("Tuple" + fields.length)), fields map (f => Select(Ident(newTermName("f")), newTermName(f.name.toString.trim))))
+    }
+
+    val evidenceClass = ClassDef(Modifiers(FINAL), newTypeName("$anon"), List(), Template(
+      List(AppliedTypeTree(Ident(newTypeName("Iso")), List(Ident(sym), mkTpt()))),
+      emptyValDef,
+      List(
+        DefDef(Modifiers(), nme.CONSTRUCTOR, List(), List(List()), TypeTree(), Block(List(Apply(Select(Super(This(tpnme.EMPTY), tpnme.EMPTY), nme.CONSTRUCTOR), List())), Literal(Constant(())))),
+        DefDef(Modifiers(), newTermName("to"), List(), List(List(ValDef(Modifiers(PARAM), newTermName("f"), Ident(sym), EmptyTree))), TypeTree(), mkFrom()))))
+    c.Expr[Iso[T, U]](Block(List(evidenceClass), Apply(Select(New(Ident(newTypeName("$anon"))), nme.CONSTRUCTOR), List())))
+  }
+}
diff --git a/test/files/run/t5923c/Test_2.scala b/test/files/run/t5923c/Test_2.scala
new file mode 100644
index 0000000000..a00f4ed7db
--- /dev/null
+++ b/test/files/run/t5923c/Test_2.scala
@@ -0,0 +1,12 @@
+// see the comments for macroExpandApply.onDelayed for an explanation of what's tested here
+object Test extends App {
+  case class Foo(i: Int, s: String, b: Boolean)
+  def foo[C, L](c: C)(implicit iso: Iso[C, L]): L = iso.to(c)
+
+  {
+    val equiv = foo(Foo(23, "foo", true))
+    def typed[T](t: => T) {}
+    typed[(Int, String, Boolean)](equiv)
+    println(equiv)
+  }
+}
\ No newline at end of file
diff --git a/test/files/run/t5923d.check b/test/files/run/t5923d.check
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/files/run/t5923d.check
diff --git a/test/files/run/t5923d/Macros_1.scala b/test/files/run/t5923d/Macros_1.scala
new file mode 100644
index 0000000000..f32d1af704
--- /dev/null
+++ b/test/files/run/t5923d/Macros_1.scala
@@ -0,0 +1,9 @@
+import scala.language.experimental.macros
+import scala.reflect.macros.Context
+
+trait MappedRow
+trait RowMapper[T <: MappedRow]
+object RowMapper {
+  implicit def mapper[T <: MappedRow]: RowMapper[T] = macro impl[T]
+  def impl[T <: MappedRow : c.WeakTypeTag](c: Context) = c.universe.reify(new RowMapper[T]{})
+}
\ No newline at end of file
diff --git a/test/files/run/t5923d/Test_2.scala b/test/files/run/t5923d/Test_2.scala
new file mode 100644
index 0000000000..6be10227c2
--- /dev/null
+++ b/test/files/run/t5923d/Test_2.scala
@@ -0,0 +1,7 @@
+class RowA extends MappedRow
+class RowB extends MappedRow
+
+object Test extends App {
+  implicitly[RowMapper[RowA]]
+  implicitly[RowMapper[RowB]]
+}
\ No newline at end of file