[nomaster] SI-7167 implicit macros decide what is divergence

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. if 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 `info.sym.isMacro` check in `typedImplicit`,
then under some circumstances (e.g. as described in 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 macro writer.

NOTE: the original commit from macro paradise also introduced a new
class, which encapsulates information about implicits in flight.
Unfortunately we cannot do that in 2.10.x, because of binary compatibility
concerns, therefore I'm marking this commit as [nomaster] and will be
resubmitting its full version in a separate pull request exclusively
targetting master.

7 files changed, 45 insertions, 16 deletions

diff --git a/src/compiler/scala/reflect/macros/runtime/Aliases.scala b/src/compiler/scala/reflect/macros/runtime/Aliases.scala
index ff870e728e..96cf50e498 100644
--- a/src/compiler/scala/reflect/macros/runtime/Aliases.scala
+++ b/src/compiler/scala/reflect/macros/runtime/Aliases.scala
@@ -28,4 +28,9 @@ 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
+
+  type ImplicitCandidate = (Type, Tree)
+  implicit class RichOpenImplicit(oi: universe.analyzer.OpenImplicit) {
+    def toImplicitCandidate = (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 be5f2dbe83..2a4a22f81c 100644
--- a/src/compiler/scala/reflect/macros/runtime/Enclosures.scala
+++ b/src/compiler/scala/reflect/macros/runtime/Enclosures.scala
@@ -13,12 +13,12 @@ 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
-  val enclosingClass: Tree                   = enclTrees collectFirst { case x: ImplDef => x } getOrElse EmptyTree
-  val enclosingImplicits: List[(Type, Tree)] = site.openImplicits
-  val enclosingMacros: List[Context]         = this :: universe.analyzer.openMacros // include self
-  val enclosingMethod: Tree                  = site.enclMethod.tree
-  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
+  val enclosingClass: Tree                        = enclTrees collectFirst { case x: ImplDef => x } getOrElse EmptyTree
+  val enclosingImplicits: List[ImplicitCandidate] = site.openImplicits.map(_.toImplicitCandidate)
+  val enclosingMacros: List[Context]              = this :: universe.analyzer.openMacros // include self
+  val enclosingMethod: Tree                       = site.enclMethod.tree
+  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 f9add91b9a..8dc9bdeb7a 100644
--- a/src/compiler/scala/reflect/macros/runtime/Typers.scala
+++ b/src/compiler/scala/reflect/macros/runtime/Typers.scala
@@ -6,7 +6,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]]
@@ -62,4 +62,4 @@ trait Typers {
   def resetAllAttrs(tree: Tree): Tree = universe.resetAllAttrs(tree)
 
   def resetLocalAttrs(tree: Tree): Tree = universe.resetLocalAttrs(tree)
-}
\ No newline at end of file
+}
diff --git a/src/compiler/scala/tools/nsc/typechecker/Contexts.scala b/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
index 6c2945cad3..3fe98ed127 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Contexts.scala
@@ -120,7 +120,7 @@ trait Contexts { self: Analyzer =>
                                                     // not inherited to child contexts
     var depth: Int = 0
     var imports: List[ImportInfo] = List()   // currently visible imports
-    var openImplicits: List[(Type,Tree)] = List()   // types for which implicit arguments
+    var openImplicits: List[OpenImplicit] = List() // types for which implicit arguments
                                              // are currently searched
     // 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 04e0b9d653..81e47eecb0 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -219,6 +219,10 @@ trait Implicits {
     override def toString = name + ": " + tpe
   }
 
+  /** 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)`
@@ -406,20 +410,32 @@ 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
            throw DivergentImplicit
          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
              typedImplicit0(info, ptChecked, isLocal)
            } catch {
              case ex: DivergentImplicit =>
                //println("DivergentImplicit for pt:"+ pt +", open implicits:"+context.openImplicits) //@MDEBUG
                if (context.openImplicits.tail.isEmpty) {
-                 if (!(pt.isErroneous))
+                 if (!pt.isErroneous && !info.sym.isMacro)
                    DivergingImplicitExpansionError(tree, pt, info.sym)(context)
                  SearchFailure
                } else {
diff --git a/src/reflect/scala/reflect/macros/Enclosures.scala b/src/reflect/scala/reflect/macros/Enclosures.scala
index c48656b366..a4ad71c348 100644
--- a/src/reflect/scala/reflect/macros/Enclosures.scala
+++ b/src/reflect/scala/reflect/macros/Enclosures.scala
@@ -29,8 +29,12 @@ trait Enclosures {
    */
   val 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.
diff --git a/src/reflect/scala/reflect/macros/Typers.scala b/src/reflect/scala/reflect/macros/Typers.scala
index 427e7854b2..d36636a6d2 100644
--- a/src/reflect/scala/reflect/macros/Typers.scala
+++ b/src/reflect/scala/reflect/macros/Typers.scala
@@ -24,8 +24,12 @@ 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.
+   *
    *  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.