advanced fresh name reification

During parsing some names are generated artificially using freshTermName & freshTypeName (e.g. `x$1`). Such names should be reified in a different way because they are assumed to be always fresh and non-overlapping with the environment. So `x$1` should reify down to equivalent of `freshTermName("x$")` rather than `TermName("x$1")`.

But this is not enough. One name can be used more than once in a tree. E.g. `q"_ + 1"` desugars into `q"x$1 => x$1 + 1"`. So we need to ensure that every place where `x$1` is used gets the same fresh name. Hence the need for `withFreshTermName` that lets q"_ + 1" quasiquote desugare into equivalent of `withFreshTermName("x$") { freshx => q"$freshx => $freshx + 1" }`.

For pattern quasiquotes it's a bit different. Due to the fact that end-result must be a pattern we need to represent fresh names as patterns too. A natural way to express that something is fresh is to represent it as a free variable (e.g. any name will do in that place). But due to possible use of the same name in multiple places we need to make sure that all such places have the same values by adding a sequence of guards to the pattern.

Previously such names were reified naively and it could have caused name collision problems and inability to properly much on trees that contain such names.

8 files changed, 126 insertions, 8 deletions

diff --git a/src/compiler/scala/tools/reflect/quasiquotes/Parsers.scala b/src/compiler/scala/tools/reflect/quasiquotes/Parsers.scala
index 7abf8b9964..ae610098dd 100644
--- a/src/compiler/scala/tools/reflect/quasiquotes/Parsers.scala
+++ b/src/compiler/scala/tools/reflect/quasiquotes/Parsers.scala
@@ -6,13 +6,14 @@ import scala.tools.nsc.ast.parser.Tokens._
 import scala.compat.Platform.EOL
 import scala.reflect.internal.util.{BatchSourceFile, SourceFile}
 import scala.collection.mutable.ListBuffer
+import scala.util.Try
 
 /** Builds upon the vanilla Scala parser and teams up together with Placeholders.scala to emulate holes.
  *  A principled solution to splicing into Scala syntax would be a parser that natively supports holes.
  *  Unfortunately, that's outside of our reach in Scala 2.11, so we have to emulate.
  */
 trait Parsers { self: Quasiquotes =>
-  import global._
+  import global.{Try => _, _}
 
   abstract class Parser extends {
     val global: self.global.type = self.global
@@ -54,7 +55,13 @@ trait Parsers { self: Quasiquotes =>
 
       def isHole(name: Name): Boolean = holeMap.contains(name)
 
+      override def freshTermName(prefix: String): TermName = unit.freshTermName(nme.QUASIQUOTE_PREFIX + prefix)
+      override def freshTypeName(prefix: String): TypeName = unit.freshTypeName(nme.QUASIQUOTE_PREFIX + prefix)
+
       override val treeBuilder = new ParserTreeBuilder {
+        override def freshTermName(prefix: String): TermName = parser.freshTermName(prefix)
+        override def freshTypeName(prefix: String): TypeName = parser.freshTypeName(prefix)
+
         // q"(..$xs)"
         override def makeTupleTerm(trees: List[Tree], flattenUnary: Boolean): Tree =
           Apply(Ident(nme.QUASIQUOTE_TUPLE), trees)
@@ -168,4 +175,14 @@ trait Parsers { self: Quasiquotes =>
       parser.treeBuilder.patvarTransformer.transform(pat)
     }
   }
+
+  object FreshName {
+    def unapply(name: Name): Option[String] =
+      name.toString.split("\\$") match {
+        case Array(qq, left, right) if qq + "$" == nme.QUASIQUOTE_PREFIX && Try(right.toInt).isSuccess =>
+          Some(left + "$")
+        case _ =>
+          None
+      }
+  }
 }
\ No newline at end of file
diff --git a/src/compiler/scala/tools/reflect/quasiquotes/Quasiquotes.scala b/src/compiler/scala/tools/reflect/quasiquotes/Quasiquotes.scala
index fb0ad3bbb0..9e98dcbc8b 100644
--- a/src/compiler/scala/tools/reflect/quasiquotes/Quasiquotes.scala
+++ b/src/compiler/scala/tools/reflect/quasiquotes/Quasiquotes.scala
@@ -47,7 +47,13 @@ abstract class Quasiquotes extends Parsers
     val tree = parse(code)
     debug(s"parsed:\n${showRaw(tree)}\n$tree\n")
     val reified = reify(tree)
-    debug(s"reified tree:\n$reified\n")
+    val sreified =
+      reified
+        .toString
+        .replace("scala.reflect.runtime.`package`.universe.build.", "")
+        .replace("scala.reflect.runtime.`package`.universe.", "")
+        .replace("scala.collection.immutable.", "")
+    debug(s"reified tree:\n$sreified\n")
     reified
   }
 }
diff --git a/src/compiler/scala/tools/reflect/quasiquotes/Reifiers.scala b/src/compiler/scala/tools/reflect/quasiquotes/Reifiers.scala
index 9f1a3ce257..642c882d5c 100644
--- a/src/compiler/scala/tools/reflect/quasiquotes/Reifiers.scala
+++ b/src/compiler/scala/tools/reflect/quasiquotes/Reifiers.scala
@@ -27,9 +27,40 @@ trait Reifiers { self: Quasiquotes =>
     def action = if (isReifyingExpressions) "splice" else "extract"
     def holesHaveTypes = isReifyingExpressions
 
+    /** Map that stores freshly generated names linked to the corresponding names in the reified tree.
+     *  This information is used to reify names created by calls to freshTermName and freshTypeName.
+     */
+    var nameMap = collection.mutable.HashMap.empty[Name, Set[TermName]].withDefault { _ => Set() }
+
+    /** Wraps expressions into:
+     *    a sequence of nested withFreshTermName/withFreshTypeName calls which are required
+     *    to force regeneration of randomly generated names on every evaluation of quasiquote.
+     *
+     *  Wraps patterns into:
+     *    a call into anonymous class' unapply method required by unapply macro expansion:
+     *
+     *      new {
+     *        def unapply(tree) = tree match {
+     *          case pattern if guard => Some(result)
+     *          case _ => None
+     *        }
+     *      }.unapply(<unapply-selector>)
+     *
+     *    where pattern corresponds to reified tree and guard represents conjunction of equalities
+     *    which check that pairs of names in nameMap.values are equal between each other.
+     */
     def wrap(tree: Tree) =
-      if (isReifyingExpressions) tree
-      else {
+      if (isReifyingExpressions) {
+        nameMap.foldLeft(tree) {
+          case (t, (origname, names)) =>
+            assert(names.size == 1)
+            val FreshName(prefix) = origname
+            val ctor = TermName("withFresh" + (if (origname.isTermName) "TermName" else "TypeName"))
+            // q"$u.build.$ctor($prefix) { ${names.head} => $t }"
+            Apply(Apply(Select(Select(u, nme.build), ctor), List(Literal(Constant(prefix)))),
+              List(Function(List(ValDef(Modifiers(PARAM), names.head, TypeTree(), EmptyTree)), t)))
+        }
+      } else {
         val freevars = holeMap.toList.map { case (name, _) => Ident(name) }
         val isVarPattern = tree match { case Bind(name, Ident(nme.WILDCARD)) => true case _ => false }
         val cases =
@@ -50,8 +81,18 @@ trait Reifiers { self: Quasiquotes =>
                 // (q"$SomeModule((..$vars))", q"$NoneModule")
                 (Apply(Ident(SomeModule), List(SyntacticTuple(vars))), Ident(NoneModule))
             }
-            // cq"$tree => $succ" :: cq"_ => $fail" :: Nil
-            CaseDef(tree, EmptyTree, succ) :: CaseDef(Ident(nme.WILDCARD), EmptyTree, fail) :: Nil
+            val guard =
+              nameMap.collect { case (_, nameset) if nameset.size >= 2 =>
+                nameset.toList.sliding(2).map { case List(n1, n2) =>
+                  // q"$n1 == $n2"
+                  Apply(Select(Ident(n1), nme.EQ), List(Ident(n2)))
+                }
+              }.flatten.reduceOption[Tree] { (l, r) =>
+                // q"$l && $r"
+                Apply(Select(l, nme.ZAND), List(r))
+              }.getOrElse { EmptyTree }
+            // cq"$tree if $guard => $succ" :: cq"_ => $fail" :: Nil
+            CaseDef(tree, guard, succ) :: CaseDef(Ident(nme.WILDCARD), EmptyTree, fail) :: Nil
           }
         // q"new { def unapply(tree: $AnyClass) = tree match { case ..$cases } }.unapply(..$args)"
         Apply(
@@ -131,6 +172,12 @@ trait Reifiers { self: Quasiquotes =>
       case Placeholder(tree, location, _) =>
         if (holesHaveTypes && !(location.tpe <:< nameType)) c.abort(tree.pos, s"$nameType expected but ${location.tpe} found")
         tree
+      case FreshName(prefix) if prefix != nme.QUASIQUOTE_NAME_PREFIX =>
+        def fresh() = c.freshName[TermName](nme.QUASIQUOTE_NAME_PREFIX)
+        def introduceName() = { val n = fresh(); nameMap(name) += n; n}
+        def result(n: Name) = if (isReifyingExpressions) Ident(n) else Bind(n, Ident(nme.WILDCARD))
+        if (isReifyingPatterns) result(introduceName())
+        else result(nameMap.get(name).map { _.head }.getOrElse { introduceName() })
       case _ =>
         super.reifyName(name)
     }
diff --git a/src/reflect/scala/reflect/api/BuildUtils.scala b/src/reflect/scala/reflect/api/BuildUtils.scala
index df126bed45..0dad78112b 100644
--- a/src/reflect/scala/reflect/api/BuildUtils.scala
+++ b/src/reflect/scala/reflect/api/BuildUtils.scala
@@ -90,6 +90,10 @@ private[reflect] trait BuildUtils { self: Universe =>
 
     def RefTree(qual: Tree, sym: Symbol): Tree
 
+    def withFreshTermName[T](prefix: String)(f: TermName => T): T
+
+    def withFreshTypeName[T](prefix: String)(f: TypeName => T): T
+
     val ScalaDot: ScalaDotExtractor
 
     trait ScalaDotExtractor {
diff --git a/src/reflect/scala/reflect/internal/BuildUtils.scala b/src/reflect/scala/reflect/internal/BuildUtils.scala
index a09715ec7c..3e04811f4d 100644
--- a/src/reflect/scala/reflect/internal/BuildUtils.scala
+++ b/src/reflect/scala/reflect/internal/BuildUtils.scala
@@ -131,6 +131,19 @@ trait BuildUtils { self: SymbolTable =>
 
     def RefTree(qual: Tree, sym: Symbol) = self.RefTree(qual, sym.name) setSymbol sym
 
+    def withFreshTermName[T](prefix: String)(f: TermName => T): T = f(TermName(freshName(prefix)))
+
+    def withFreshTypeName[T](prefix: String)(f: TypeName => T): T = f(TypeName(freshName(prefix)))
+
+    object freshName {
+      private val counters = collection.mutable.HashMap[String, Int]() withDefaultValue 0
+      def apply(prefix: String): String = {
+        val safePrefix = prefix.replaceAll("""[<>]""", """\$""")
+        counters(safePrefix) += 1
+        safePrefix + counters(safePrefix)
+      }
+    }
+
     object FlagsRepr extends FlagsReprExtractor {
       def apply(bits: Long): FlagSet = bits
       def unapply(flags: Long): Some[Long] = Some(flags)
diff --git a/src/reflect/scala/reflect/internal/StdNames.scala b/src/reflect/scala/reflect/internal/StdNames.scala
index 7cfe194fd1..5cc3f911a4 100644
--- a/src/reflect/scala/reflect/internal/StdNames.scala
+++ b/src/reflect/scala/reflect/internal/StdNames.scala
@@ -320,6 +320,7 @@ trait StdNames {
     val REIFY_FREE_VALUE_SUFFIX: NameType  = "$value"
     val REIFY_SYMDEF_PREFIX: NameType      = "symdef$"
     val QUASIQUOTE_PREFIX: String          = "qq$"
+    val QUASIQUOTE_NAME_PREFIX: String     = "nn$"
     val QUASIQUOTE_FILE: String            = "<quasiquote>"
     val QUASIQUOTE_TUPLE: NameType         = "$quasiquote$tuple$"
     val QUASIQUOTE_CASE: NameType          = "$quasiquote$case$"
diff --git a/test/files/scalacheck/quasiquotes/TermConstructionProps.scala b/test/files/scalacheck/quasiquotes/TermConstructionProps.scala
index 753ad1aa59..9284903623 100644
--- a/test/files/scalacheck/quasiquotes/TermConstructionProps.scala
+++ b/test/files/scalacheck/quasiquotes/TermConstructionProps.scala
@@ -7,7 +7,6 @@ import scala.reflect.runtime.universe._
 import Flag._
 
 object TermConstructionProps extends QuasiquoteProperties("term construction") {
-
   property("splice single tree return tree itself") = forAll { (t: Tree) =>
     q"$t" ≈ t
   }
@@ -191,4 +190,13 @@ object TermConstructionProps extends QuasiquoteProperties("term construction") {
     val assignx = q"x = 1"
     assertEqAst(q"f($assignx)", "f(x = 1)")
   }
+
+  property("fresh names are regenerated at each evaluation") = test {
+    def plusOne = q"{ _ + 1 }"
+    assert(!(plusOne ≈ plusOne))
+    def whileTrue = q"while(true) false"
+    assert(!(whileTrue ≈ whileTrue))
+    def withEvidence = q"def foo[T: X]"
+    assert(!(withEvidence ≈ withEvidence))
+  }
 }
diff --git a/test/files/scalacheck/quasiquotes/TermDeconstructionProps.scala b/test/files/scalacheck/quasiquotes/TermDeconstructionProps.scala
index 22d4b1ce4f..ff105f7fba 100644
--- a/test/files/scalacheck/quasiquotes/TermDeconstructionProps.scala
+++ b/test/files/scalacheck/quasiquotes/TermDeconstructionProps.scala
@@ -88,7 +88,7 @@ object TermDeconstructionProps extends QuasiquoteProperties("term deconstruction
     matches("new foo with bar")
     matches("new foo with bar { body }")
     matches("new { anonymous }")
-    matches("new { val early = 1} with Parent[Int] { body }")
+    matches("new { val early = 1 } with Parent[Int] { body }")
     matches("new Foo { selfie => }")
   }
 
@@ -111,4 +111,26 @@ object TermDeconstructionProps extends QuasiquoteProperties("term deconstruction
     assert(left ≈ q"foo(bar)")
     assert(value ≈ q"baz")
   }
+
+  property("deconstruct while loop") = test {
+    val q"while($cond) $body" = parse("while(cond) body")
+    assert(cond ≈ q"cond")
+    assert(body ≈ q"body")
+  }
+
+  property("deconstruct do while loop") = test {
+    val q"do $body while($cond)" = parse("do body while(cond)")
+    assert(cond ≈ q"cond")
+    assert(body ≈ q"body")
+  }
+
+  property("deconstruct anonymous function with placeholders") = test {
+    val q"{ $f(_) }" = q"{ foo(_) }"
+    assert(f ≈ q"foo")
+    val q"{ _.$member }" = q"{ _.foo }"
+    assert(member ≈ TermName("foo"))
+    val q"{ _ + $x }" = q"{ _ + x }"
+    assert(x ≈ q"x")
+    val q"{ _ * _ }" = q"{ _ * _ }"
+  }
 }