Merge pull request #2514 from scalamacros/topic/5923-master

makes sense of implicit macros! now in master

10 files changed, 111 insertions, 62 deletions

diff --git a/src/compiler/scala/reflect/macros/runtime/Aliases.scala b/src/compiler/scala/reflect/macros/runtime/Aliases.scala
index ff870e728e..1c6703aeee 100644
--- a/src/compiler/scala/reflect/macros/runtime/Aliases.scala
+++ b/src/compiler/scala/reflect/macros/runtime/Aliases.scala
@@ -28,4 +28,8 @@ trait Aliases {
   override def typeTag[T](implicit ttag: TypeTag[T]) = ttag
   override def weakTypeOf[T](implicit attag: WeakTypeTag[T]): Type = attag.tpe
   override def typeOf[T](implicit ttag: TypeTag[T]): Type = ttag.tpe
+
+  implicit class RichOpenImplicit(oi: universe.analyzer.OpenImplicit) {
+    def toImplicitCandidate = ImplicitCandidate(oi.info.pre, oi.info.sym, oi.pt, oi.tree)
+  }
 }
\ No newline at end of file
diff --git a/src/compiler/scala/reflect/macros/runtime/Enclosures.scala b/src/compiler/scala/reflect/macros/runtime/Enclosures.scala
index 8fe0b09700..f3f92550de 100644
--- a/src/compiler/scala/reflect/macros/runtime/Enclosures.scala
+++ b/src/compiler/scala/reflect/macros/runtime/Enclosures.scala
@@ -21,16 +21,16 @@ trait Enclosures {
 
   // vals are eager to simplify debugging
   // after all we wouldn't save that much time by making them lazy
-  val macroApplication: Tree                 = expandee
-  def enclosingPackage: PackageDef           = strictEnclosure[PackageDef]
-  val enclosingClass: Tree                   = lenientEnclosure[ImplDef]
-  def enclosingImpl: ImplDef                 = strictEnclosure[ImplDef]
-  def enclosingTemplate: Template            = strictEnclosure[Template]
-  val enclosingImplicits: List[(Type, Tree)] = site.openImplicits
-  val enclosingMacros: List[Context]         = this :: universe.analyzer.openMacros // include self
-  val enclosingMethod: Tree                  = lenientEnclosure[DefDef]
-  def enclosingDef: DefDef                   = strictEnclosure[DefDef]
-  val enclosingPosition: Position            = if (enclPoses.isEmpty) NoPosition else enclPoses.head.pos
-  val enclosingUnit: CompilationUnit         = universe.currentRun.currentUnit
-  val enclosingRun: Run                      = universe.currentRun
+  val macroApplication: Tree                      = expandee
+  def enclosingPackage: PackageDef                = strictEnclosure[PackageDef]
+  val enclosingClass: Tree                        = lenientEnclosure[ImplDef]
+  def enclosingImpl: ImplDef                      = strictEnclosure[ImplDef]
+  def enclosingTemplate: Template                 = strictEnclosure[Template]
+  val enclosingImplicits: List[ImplicitCandidate] = site.openImplicits.map(_.toImplicitCandidate)
+  val enclosingMacros: List[Context]              = this :: universe.analyzer.openMacros // include self
+  val enclosingMethod: Tree                       = lenientEnclosure[DefDef]
+  def enclosingDef: DefDef                        = strictEnclosure[DefDef]
+  val enclosingPosition: Position                 = if (enclPoses.isEmpty) NoPosition else enclPoses.head.pos
+  val enclosingUnit: CompilationUnit              = universe.currentRun.currentUnit
+  val enclosingRun: Run                           = universe.currentRun
 }
diff --git a/src/compiler/scala/reflect/macros/runtime/Typers.scala b/src/compiler/scala/reflect/macros/runtime/Typers.scala
index 398770ab35..4592f640bd 100644
--- a/src/compiler/scala/reflect/macros/runtime/Typers.scala
+++ b/src/compiler/scala/reflect/macros/runtime/Typers.scala
@@ -8,7 +8,7 @@ trait Typers {
 
   def openMacros: List[Context] = this :: universe.analyzer.openMacros
 
-  def openImplicits: List[(Type, Tree)] = callsiteTyper.context.openImplicits
+  def openImplicits: List[ImplicitCandidate] = callsiteTyper.context.openImplicits.map(_.toImplicitCandidate)
 
   /**
    * @see [[scala.tools.reflect.ToolBox.typeCheck]]
@@ -37,30 +37,13 @@ trait Typers {
 
   def inferImplicitValue(pt: Type, silent: Boolean = true, withMacrosDisabled: Boolean = false, pos: Position = enclosingPosition): Tree = {
     macroLogVerbose("inferring implicit value of type %s, macros = %s".format(pt, !withMacrosDisabled))
-    inferImplicit(universe.EmptyTree, pt, isView = false, silent = silent, withMacrosDisabled = withMacrosDisabled, pos = pos)
+    universe.analyzer.inferImplicit(universe.EmptyTree, pt, false, callsiteTyper.context, silent, withMacrosDisabled, pos, (pos, msg) => throw TypecheckException(pos, msg))
   }
 
   def inferImplicitView(tree: Tree, from: Type, to: Type, silent: Boolean = true, withMacrosDisabled: Boolean = false, pos: Position = enclosingPosition): Tree = {
     macroLogVerbose("inferring implicit view from %s to %s for %s, macros = %s".format(from, to, tree, !withMacrosDisabled))
     val viewTpe = universe.appliedType(universe.definitions.FunctionClass(1).toTypeConstructor, List(from, to))
-    inferImplicit(tree, viewTpe, isView = true, silent = silent, withMacrosDisabled = withMacrosDisabled, pos = pos)
-  }
-
-  private def inferImplicit(tree: Tree, pt: Type, isView: Boolean, silent: Boolean, withMacrosDisabled: Boolean, pos: Position): Tree = {
-    import universe.analyzer.SearchResult
-    val context = callsiteTyper.context
-    val wrapper1 = if (!withMacrosDisabled) (context.withMacrosEnabled[SearchResult] _) else (context.withMacrosDisabled[SearchResult] _)
-    def wrapper (inference: => SearchResult) = wrapper1(inference)
-    wrapper(universe.analyzer.inferImplicit(tree, pt, reportAmbiguous = true, isView = isView, context = context, saveAmbiguousDivergent = !silent, pos = pos)) match {
-      case failure if failure.tree.isEmpty =>
-        macroLogVerbose("implicit search has failed. to find out the reason, turn on -Xlog-implicits")
-        context.firstError match {
-          case Some(err) => throw new TypecheckException(err.errPos, err.errMsg)
-          case None      => universe.EmptyTree
-        }
-      case success =>
-        success.tree
-    }
+    universe.analyzer.inferImplicit(tree, viewTpe, true, callsiteTyper.context, silent, withMacrosDisabled, pos, (pos, msg) => throw TypecheckException(pos, msg))
   }
 
   def resetAllAttrs(tree: Tree): Tree = universe.resetAllAttrs(tree)
diff --git a/src/compiler/scala/tools/nsc/typechecker/Contexts.scala b/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
index e3bb595bd7..82e6de87e3 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
@@ -213,7 +213,7 @@ trait Contexts { self: Analyzer =>
     def isRootImport: Boolean = false
 
     /** Types for which implicit arguments are currently searched */
-    var openImplicits: List[(Type,Tree)] = List()
+    var openImplicits: List[OpenImplicit] = List()
 
     /* For a named application block (`Tree`) the corresponding `NamedApplyInfo`. */
     var namedApplyBlockInfo: Option[(Tree, NamedApplyInfo)] = None
diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index f27c15180e..05db86635a 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -100,6 +100,21 @@ trait Implicits {
     result
   }
 
+  /** A friendly wrapper over inferImplicit to be used in macro contexts and toolboxes.
+   */
+  def inferImplicit(tree: Tree, pt: Type, isView: Boolean, context: Context, silent: Boolean, withMacrosDisabled: Boolean, pos: Position, onError: (Position, String) => Unit): Tree = {
+    val wrapper1 = if (!withMacrosDisabled) (context.withMacrosEnabled[SearchResult] _) else (context.withMacrosDisabled[SearchResult] _)
+    def wrapper(inference: => SearchResult) = wrapper1(inference)
+    val result = wrapper(inferImplicit(tree, pt, reportAmbiguous = true, isView = isView, context = context, saveAmbiguousDivergent = !silent, pos = pos))
+    if (result.isFailure && !silent) {
+      val err = context.firstError
+      val errPos = err.map(_.errPos).getOrElse(pos)
+      val errMsg = err.map(_.errMsg).getOrElse("implicit search has failed. to find out the reason, turn on -Xlog-implicits")
+      onError(errPos, errMsg)
+    }
+    result.tree
+  }
+
   /** Find all views from type `tp` (in which `tpars` are free)
    *
    * Note that the trees in the search results in the returned list share the same type variables.
@@ -224,6 +239,10 @@ trait Implicits {
     )
   }
 
+  /** A class which is used to track pending implicits to prevent infinite implicit searches.
+   */
+  case class OpenImplicit(info: ImplicitInfo, pt: Type, tree: Tree)
+
   /** A sentinel indicating no implicit was found */
   val NoImplicitInfo = new ImplicitInfo(null, NoType, NoSymbol) {
     // equals used to be implemented in ImplicitInfo with an `if(this eq NoImplicitInfo)`
@@ -407,13 +426,25 @@ trait Implicits {
      *  @pre           `info.tpe` does not contain an error
      */
     private def typedImplicit(info: ImplicitInfo, ptChecked: Boolean, isLocal: Boolean): SearchResult = {
-      (context.openImplicits find { case (tp, tree1) => tree1.symbol == tree.symbol && dominates(pt, tp)}) match {
+      // SI-7167 let implicit macros decide what amounts for a divergent implicit search
+      // imagine a macro writer which wants to synthesize a complex implicit Complex[T] by making recursive calls to Complex[U] for its parts
+      // e.g. we have `class Foo(val bar: Bar)` and `class Bar(val x: Int)`
+      // then it's quite reasonable for the macro writer to synthesize Complex[Foo] by calling `inferImplicitValue(typeOf[Complex[Bar])`
+      // however if we didn't insert the `info.sym.isMacro` check here, then under some circumstances
+      // (e.g. as described here http://groups.google.com/group/scala-internals/browse_thread/thread/545462b377b0ac0a)
+      // `dominates` might decide that `Bar` dominates `Foo` and therefore a recursive implicit search should be prohibited
+      // now when we yield control of divergent expansions to the macro writer, what happens next?
+      // in the worst case, if the macro writer is careless, we'll get a StackOverflowException from repeated macro calls
+      // otherwise, the macro writer could check `c.openMacros` and `c.openImplicits` and do `c.abort` when expansions are deemed to be divergent
+      // upon receiving `c.abort` the typechecker will decide that the corresponding implicit search has failed
+      // which will fail the entire stack of implicit searches, producing a nice error message provided by the programmer
+      (context.openImplicits find { case OpenImplicit(info, tp, tree1) => !info.sym.isMacro && tree1.symbol == tree.symbol && dominates(pt, tp)}) match {
          case Some(pending) =>
            //println("Pending implicit "+pending+" dominates "+pt+"/"+undetParams) //@MDEBUG
            DivergentSearchFailure
          case None =>
            try {
-             context.openImplicits = (pt, tree) :: context.openImplicits
+             context.openImplicits = OpenImplicit(info, pt, tree) :: context.openImplicits
              // println("  "*context.openImplicits.length+"typed implicit "+info+" for "+pt) //@MDEBUG
              val result = typedImplicit0(info, ptChecked, isLocal)
              if (result.isDivergent) {
diff --git a/src/compiler/scala/tools/nsc/typechecker/Macros.scala b/src/compiler/scala/tools/nsc/typechecker/Macros.scala
index d07297bb35..ecae55562b 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Macros.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Macros.scala
@@ -394,7 +394,7 @@ trait Macros extends scala.tools.reflect.FastTrack with Traces {
             case Fallback(fallback) =>
               typer.typed1(fallback, EXPRmode, WildcardType)
             case Delayed(delayed) =>
-              delayed
+              typer.instantiate(delayed, EXPRmode, WildcardType)
             case Skipped(skipped) =>
               skipped
             case Failure(failure) =>
@@ -778,6 +778,29 @@ trait Macros extends scala.tools.reflect.FastTrack with Traces {
           expanded2
         }
       }
+      override def onDelayed(delayed: Tree) = {
+        // If we've been delayed (i.e. bailed out of the expansion because of undetermined type params present in the expandee),
+        // then there are two possible situations we're in:
+        // 1) We're in POLYmode, when the typer tests the waters wrt type inference
+        // (e.g. as in typedArgToPoly in doTypedApply).
+        // 2) We're out of POLYmode, which means that the typer is out of tricks to infer our type
+        // (e.g. if we're an argument to a function call, then this means that no previous argument lists
+        // can determine our type variables for us).
+        //
+        // Situation #1 is okay for us, since there's no pressure. In POLYmode we're just verifying that
+        // there's nothing outrageously wrong with our undetermined type params (from what I understand!).
+        //
+        // Situation #2 requires measures to be taken. If we're in it, then noone's going to help us infer
+        // the undetermined type params. Therefore we need to do something ourselves or otherwise this
+        // expandee will forever remaing not expanded (see SI-5692). A traditional way out of this conundrum
+        // is to call `instantiate` and let the inferencer try to find the way out. It works for simple cases,
+        // but sometimes, if the inferencer lacks information, it will be forced to approximate. This prevents
+        // an important class of macros, fundep materializers, from working, which I perceive is a problem we need to solve.
+        // For details see SI-7470.
+        val shouldInstantiate = typer.context.undetparams.nonEmpty && !mode.inPolyMode
+        if (shouldInstantiate) typer.instantiatePossiblyExpectingUnit(delayed, mode, pt)
+        else delayed
+      }
     }
     expander(expandee)
   }
diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
index 001808e6bc..2de59056ef 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala
@@ -1091,7 +1091,6 @@ trait Typers extends Adaptations with Tags {
           instantiateToMethodType(mt)
 
         case _ =>
-        def vanillaAdapt(tree: Tree) = {
           def shouldInsertApply(tree: Tree) = mode.inAll(EXPRmode | FUNmode) && (tree.tpe match {
             case _: MethodType | _: OverloadedType | _: PolyType => false
             case _                                               => applyPossible
@@ -1107,16 +1106,15 @@ trait Typers extends Adaptations with Tags {
           }
           if (tree.isType)
             adaptType()
+          else if (mode.inExprModeButNot(FUNmode) && treeInfo.isMacroApplication(tree))
+            macroExpandApply(this, tree, mode, pt)
           else if (mode.inAll(PATTERNmode | FUNmode))
             adaptConstrPattern()
           else if (shouldInsertApply(tree))
             insertApply()
-          else if (!context.undetparams.isEmpty && !mode.inPolyMode) { // (9)
+          else if (context.undetparams.nonEmpty && !mode.inPolyMode) { // (9)
             assert(!mode.inHKMode, mode) //@M
-            if (mode.inExprModeButNot(FUNmode) && pt.typeSymbol == UnitClass)
-              instantiateExpectingUnit(tree, mode)
-            else
-              instantiate(tree, mode, pt)
+            instantiatePossiblyExpectingUnit(tree, mode, pt)
           } else if (tree.tpe <:< pt) {
             tree
           } else {
@@ -1242,9 +1240,6 @@ trait Typers extends Adaptations with Tags {
             fallBack
           }
       }
-        val tree1 = if (mode.inExprModeButNot(FUNmode) && treeInfo.isMacroApplication(tree)) macroExpandApply(this, tree, mode, pt) else tree
-        if (tree == tree1) vanillaAdapt(tree1) else tree1
-    }
     }
 
     def instantiate(tree: Tree, mode: Mode, pt: Type): Tree = {
@@ -1264,6 +1259,13 @@ trait Typers extends Adaptations with Tags {
       }
     }
 
+    def instantiatePossiblyExpectingUnit(tree: Tree, mode: Mode, pt: Type): Tree = {
+      if (mode.inExprModeButNot(FUNmode) && pt.typeSymbol == UnitClass)
+        instantiateExpectingUnit(tree, mode)
+      else
+        instantiate(tree, mode, pt)
+    }
+
     private def isAdaptableWithView(qual: Tree) = {
       val qtpe = qual.tpe.widen
       (    !isPastTyper
diff --git a/src/compiler/scala/tools/reflect/ToolBoxFactory.scala b/src/compiler/scala/tools/reflect/ToolBoxFactory.scala
index 7f7bcd70d2..f81ec610ef 100644
--- a/src/compiler/scala/tools/reflect/ToolBoxFactory.scala
+++ b/src/compiler/scala/tools/reflect/ToolBoxFactory.scala
@@ -181,16 +181,7 @@ abstract class ToolBoxFactory[U <: JavaUniverse](val u: U) { factorySelf =>
         transformDuringTyper(tree, withImplicitViewsDisabled = false, withMacrosDisabled = withMacrosDisabled)(
           (currentTyper, tree) => {
             trace("inferring implicit %s (macros = %s): ".format(if (isView) "view" else "value", !withMacrosDisabled))(showAttributed(pt, true, true, settings.Yshowsymkinds.value))
-            val context = currentTyper.context
-            val result = analyzer.inferImplicit(tree, pt, reportAmbiguous = true, isView = isView, context = context, saveAmbiguousDivergent = !silent, pos = pos)
-            if (result.isFailure) {
-              // @H: what's the point of tracing an empty tree?
-              trace("implicit search has failed. to find out the reason, turn on -Xlog-implicits: ")(result.tree)
-              context.firstError foreach { err =>
-                throw ToolBoxError("reflective implicit search has failed: %s".format(err.errMsg))
-              }
-            }
-            result.tree
+            analyzer.inferImplicit(tree, pt, isView, currentTyper.context, silent, withMacrosDisabled, pos, (pos, msg) => throw ToolBoxError(msg))
           })
 
       def compile(expr0: Tree): () => Any = {
diff --git a/src/reflect/scala/reflect/macros/Enclosures.scala b/src/reflect/scala/reflect/macros/Enclosures.scala
index 8ea05500e4..d6ba5f39cd 100644
--- a/src/reflect/scala/reflect/macros/Enclosures.scala
+++ b/src/reflect/scala/reflect/macros/Enclosures.scala
@@ -45,13 +45,17 @@ trait Enclosures {
    */
   def enclosingMacros: List[Context]
 
-  /** Types along with corresponding trees for which implicit arguments are currently searched.
+  /** Information about one of the currently considered implicit candidates.
+   *  Candidates are used in plural form, because implicit parameters may themselves have implicit parameters,
+   *  hence implicit searches can recursively trigger other implicit searches.
+   *
    *  Can be useful to get information about an application with an implicit parameter that is materialized during current macro expansion.
+   *  If we're in an implicit macro being expanded, it's included in this list.
    *
    *  Unlike `openImplicits`, this is a val, which means that it gets initialized when the context is created
    *  and always stays the same regardless of whatever happens during macro expansion.
    */
-  def enclosingImplicits: List[(Type, Tree)]
+  def enclosingImplicits: List[ImplicitCandidate]
 
   /** Tries to guess a position for the enclosing application.
    *  But that is simple, right? Just dereference `pos` of `macroApplication`? Not really.
diff --git a/src/reflect/scala/reflect/macros/Typers.scala b/src/reflect/scala/reflect/macros/Typers.scala
index eaf79f2dab..d7aec9b3ef 100644
--- a/src/reflect/scala/reflect/macros/Typers.scala
+++ b/src/reflect/scala/reflect/macros/Typers.scala
@@ -11,8 +11,6 @@ package macros
 trait Typers {
   self: Context =>
 
-  import universe._
-
   /** Contexts that represent macros in-flight, including the current one. Very much like a stack trace, but for macros only.
    *  Can be useful for interoperating with other macros and for imposing compiler-friendly limits on macro expansion.
    *
@@ -25,13 +23,26 @@ trait Typers {
    */
   def openMacros: List[Context]
 
-  /** Types along with corresponding trees for which implicit arguments are currently searched.
+  /** Information about one of the currently considered implicit candidates.
+   *  Candidates are used in plural form, because implicit parameters may themselves have implicit parameters,
+   *  hence implicit searches can recursively trigger other implicit searches.
+   *
+   *  `pre` and `sym` provide information about the candidate itself.
+   *  `pt` and `tree` store the parameters of the implicit search the candidate is participating in.
+   */
+  case class ImplicitCandidate(pre: Type, sym: Symbol, pt: Type, tree: Tree)
+
+  /** Information about one of the currently considered implicit candidates.
+   *  Candidates are used in plural form, because implicit parameters may themselves have implicit parameters,
+   *  hence implicit searches can recursively trigger other implicit searches.
+   *
    *  Can be useful to get information about an application with an implicit parameter that is materialized during current macro expansion.
+   *  If we're in an implicit macro being expanded, it's included in this list.
    *
    *  Unlike `enclosingImplicits`, this is a def, which means that it gets recalculated on every invocation,
    *  so it might change depending on what is going on during macro expansion.
    */
-  def openImplicits: List[(Type, Tree)]
+  def openImplicits: List[ImplicitCandidate]
 
   /** Typechecks the provided tree against the expected type `pt` in the macro callsite context.
    *
@@ -46,7 +57,7 @@ trait Typers {
    *
    *  @throws [[scala.reflect.macros.TypecheckException]]
    */
-  def typeCheck(tree: Tree, pt: Type = WildcardType, silent: Boolean = false, withImplicitViewsDisabled: Boolean = false, withMacrosDisabled: Boolean = false): Tree
+  def typeCheck(tree: Tree, pt: Type = universe.WildcardType, silent: Boolean = false, withImplicitViewsDisabled: Boolean = false, withMacrosDisabled: Boolean = false): Tree
 
   /** Infers an implicit value of the expected type `pt` in the macro callsite context.
    *  Optional `pos` parameter provides a position that will be associated with the implicit search.