Verilog renaming uses "_", works on whole AST

Summary of changes to firrtl.passes.VerilogRename:
  - Use "_" to mangle names that conflict with Verilog
    keywords (previously "$")
  - Rewrite to operate on the whole AST to propogate mangled ports and
    module names
  - Make VerilogRename a Transform (was previously a Pass)
  - Renames are now propagated
  - Adds documentation for new VerilogRename

This makes the VerilogRename Transform (previously a Pass) use an
underscore ('_') instead of a dollar sign ('$') to mangle names that
conflict with Verilog keywords. This prevents problems with potentially
buggy tools that are not expecting '$' in Verilog names.

This reimplements VerilogRename to be safe for name collisions that may
occur anywhere in the AST, e.g., in ports, module names, circuit names, or
in any statements/expressions. Previously, names were only mangled in
statements and in place. This resulted in problems where renames of ports
in a child's namespace would not be guaranteed to be mangled the same way
in a parent's namespace. The algorithm is reimplemented to walk all
modules in reverse topological order (from leafs to main) and relying on a
RenameMap to track name changes.

Signed-off-by: Schuyler Eldridge <schuyler.eldridge@ibm.com>

2 files changed, 232 insertions, 12 deletions

diff --git a/src/main/scala/firrtl/passes/Passes.scala b/src/main/scala/firrtl/passes/Passes.scala
index 5e5aa26a..969701d2 100644
--- a/src/main/scala/firrtl/passes/Passes.scala
+++ b/src/main/scala/firrtl/passes/Passes.scala
@@ -9,6 +9,8 @@ import firrtl.Utils._
 import firrtl.Mappers._
 import firrtl.PrimOps._
 import firrtl.transforms.ConstantPropagation
+import firrtl.annotations.{Named, CircuitName, ModuleName, ComponentName}
+import firrtl.analyses.InstanceGraph
 
 import scala.collection.mutable
 
@@ -247,23 +249,204 @@ object Legalize extends Pass {
   }
 }
 
-object VerilogRename extends Pass {
-  def verilogRenameN(n: String): String =
-    if (v_keywords(n)) "%s$".format(n) else n
+/** Transform that removes collisions with Verilog keywords
+  * @define implicitRename @param renames the [[RenameMap]] to query when renaming
+  * @define implicitNamespace @param ns an encolosing [[Namespace]] with which new names must not conflict
+  * @define implicitScope @param scope the enclosing scope of this name. If [[None]], then this is a [[Circuit]] name
+  */
+object VerilogRename extends Transform {
+  def inputForm: CircuitForm = LowForm
+  def outputForm: CircuitForm = LowForm
+  type Renames = mutable.HashMap[String, String]
+  private val inlineDelim = "_"
+
+  /** Generate a new name, by appending underscores, that will not conflict with the existing namespace
+    * @param n a name
+    * @param ns a [[Namespace]]
+    * @return a conflict-free name
+    * @note prefix uniqueness is not respected
+    */
+  private def safeName(n: String, ns: Namespace): String =
+    Uniquify.findValidPrefix(n + inlineDelim, Seq(""), ns.cloneUnderlying ++ v_keywords)
+
+  /** Modify a name to not conflict with a Verilog keywords while respecting existing renames and a namespace
+    * @param n the name to rename
+    * @param renames the [[RenameMap]] to query when renaming
+    * $implicitRename
+    * $implicitNamespace
+    * $implicitScope
+    * @return a name without keyword conflicts
+    */
+  private def onName(n: String)(implicit renames: RenameMap, ns: Namespace, scope: Option[Named]): String = {
+
+    // Convert a [[String]] into [[Named]] based on the provided scope.
+    def wrap(name: String, scope: Option[Named]): Named = scope match {
+      case None                     => CircuitName(name)
+      case Some(cir: CircuitName)   => ModuleName(name, cir)
+      case Some(mod: ModuleName)    => ComponentName(name, mod)
+      case Some(com: ComponentName) => ComponentName(s"${com.name}.$name", com.module)
+    }
+
+    val named = wrap(n, scope)
+
+    // If this has already been renamed use that name. If it conflicts with a keyword, determine a new, safe name and
+    // update the renames. Otherwise, leave it alone.
+    val namedx: Seq[Named] = renames.get(named) match {
+      case Some(x) => x
+      case None if v_keywords(n) =>
+        val sn = wrap(safeName(n, ns), scope)
+        renames.rename(named, sn)
+        Seq(sn)
+      case _ => Seq(wrap(n, scope))
+    }
+
+    namedx match {
+      case ComponentName(n, _) :: Nil => n
+      case ModuleName(n, _)    :: Nil => n
+      case CircuitName(n)      :: Nil => n
+      case x => throw new PassException(
+        s"Verilog renaming shouldn't result in multiple renames, but found '$named -> $namedx'")
+    }
+  }
+
+  /** Rename the fields of a [[Type]] to match the ports of an instance
+    * @param t the type to rename
+    * $implicitRename
+    * $implicitNamespace
+    * $implicitScope
+    * @return a [[Type]] with updated names
+    * @note This is not intended for fixing arbitrary types, only [[BundleType]] in instance [[WRef]]s
+    */
+  private def onType(t: Type)
+                    (implicit renames: RenameMap, ns: Namespace, scope: Option[ModuleName]): Type = t match {
+    case b: BundleType => b.copy(fields = b.fields.map(f => f.copy(name = onName(f.name))))
+    case _             => t
+  }
+
+  /** Rename an [[Expression]] to respect existing renames and avoid keyword collisions
+    * @param e the [[Expression]] to rename
+    * $implicitRename
+    * $implicitNamespace
+    * $implicitScope
+    * @return an [[Expression]] without keyword conflicts
+    */
+  private def onExpression(e: Expression)
+                          (implicit renames: RenameMap, ns: Namespace, scope: Option[ModuleName],
+                           iToM: mutable.Map[ComponentName, ModuleName]): Expression = e match {
+    case wsf@ WSubField(wr@ WRef(name, _, InstanceKind, _), port, _, _) =>
+      val subInst = ComponentName(name, scope.get)
+      val subModule = iToM(subInst)
+      val subPort = ComponentName(port, subModule)
+
+      val wrx = wr.copy(
+        name = renames.get(subInst).orElse(Some(Seq(subInst))).get.head.name,
+        tpe = onType(wr.tpe)(renames, ns, Some(subModule)))
 
-  def verilogRenameE(e: Expression): Expression = e match {
-    case ex: WRef => ex copy (name = verilogRenameN(ex.name))
-    case ex => ex map verilogRenameE
+      wsf.copy(
+        expr = wrx,
+        name = renames.get(subPort).orElse(Some(Seq(subPort))).get.head.name)
+    case wr: WRef => wr.copy(name=onName(wr.name))
+    case ex       => ex.map(onExpression)
   }
 
-  def verilogRenameS(s: Statement): Statement =
-    s map verilogRenameS map verilogRenameE map verilogRenameN
+  /** Rename a [[Statement]] to respect existing renames and avoid keyword collisions
+    * $implicitRename
+    * $implicitNamespace
+    * $implicitScope
+    * @return a [[Statement]] without keyword conflicts
+    */
+  private def onStatement(s: Statement)
+                         (implicit renames: RenameMap, ns: Namespace, scope: Option[ModuleName],
+                          iToM: mutable.Map[ComponentName, ModuleName]): Statement = s match {
+    case wdi: WDefInstance =>
+      val subModule = ModuleName(wdi.module, scope.get.circuit)
+      val modulex = renames.get(subModule).orElse(Some(Seq(subModule))).get.head.name
+      val wdix = wdi.copy(module = modulex,
+                          name = onName(wdi.name),
+                          tpe = onType(wdi.tpe)(renames, ns, Some(ModuleName(modulex, scope.get.circuit))))
+      iToM(ComponentName(wdi.name, scope.get)) = ModuleName(wdix.module, scope.get.circuit)
+      wdix
+    case _ => s
+        .map(onStatement)
+        .map(onExpression)
+        .map(onName)
+  }
+
+  /** Rename a [[Port]] to avoid keyword collisions
+    * $implicitRename
+    * $implicitNamespace
+    * $implicitScope
+    * @return a [[Port]] without keyword conflicts
+    */
+  private def onPort(p: Port)(implicit renames: RenameMap, ns: Namespace, scope: Option[ModuleName]): Port =
+    p.copy(name = onName(p.name))
+
+  /** Rename a [[DefModule]] and it's internals (ports and statements) to fix keyword collisions and update instance
+    * references to respect previous renames
+    * @param renames a [[RenameMap]]
+    * @param circuit the enclosing [[CircuitName]]
+    * @return a [[DefModule]] without keyword conflicts
+    */
+  private def onModule(renames: RenameMap, circuit: CircuitName)(m: DefModule): DefModule = {
+    implicit val moduleNamespace: Namespace = Namespace(m)
+    implicit val scope: Option[ModuleName] = Some(ModuleName(m.name, circuit))
+    implicit val r: RenameMap = renames
+
+    // Store local renames of refs to instances to their renamed modules. This is needed when renaming port connections
+    // on subfields where only the local instance name is available.
+    implicit val iToM: mutable.Map[ComponentName, ModuleName] = mutable.Map.empty
 
-  def verilogRenameP(p: Port): Port =
-    p copy (name = verilogRenameN(p.name))
+    m
+      .map(onPort)
+      .map(onStatement)
+      .map(onName(_: String)(renames, moduleNamespace, Some(circuit)))
+  }
+
+  /** Fix any Verilog keyword collisions in a [[Circuit]]
+    * @param c a [[Circuit]] with possible name collisions
+    * @param renames a [[RenameMap]] to update. If you don't want to propagate renames, this can be ignored.
+    * @return a [[Circuit]] without keyword conflicts
+    */
+  def run(c: Circuit, renames: RenameMap = RenameMap()): Circuit = {
+    implicit val circuitNamespace: Namespace = Namespace(c)
+    implicit val scope: Option[CircuitName] = Some(CircuitName(c.main))
 
-  def run(c: Circuit): Circuit =
-    c copy (modules = c.modules map (_ map verilogRenameP map verilogRenameS))
+    // Rename all modules from leafs to root in one pass while updating a shared rename map. Going from leafs to roots
+    // ensures that the rename map is safe for parents to blindly consult.
+    val modulesx: Map[ModuleName, Seq[DefModule]] = new InstanceGraph(c).moduleOrder.reverse
+      .map(onModule(renames, scope.get))
+      .groupBy(m => ModuleName(m.name, scope.get))
+
+    // Reorder the renamed modules into the original circuit order.
+    val modulesxx: Seq[DefModule] = c.modules.flatMap{ orig =>
+      val named = ModuleName(orig.name, scope.get)
+      modulesx(renames.get(named).orElse(Some(Seq(named))).get.head)
+    }
+
+    // Rename the circuit if the top module was renamed
+    val mainx = renames.get(ModuleName(c.main, CircuitName(c.main))) match {
+      case Some(ModuleName(m, _) :: Nil) =>
+        renames.rename(CircuitName(c.main), CircuitName(m))
+        m
+      case x@ Some(car :: cdr) => throw new PassException(
+        s"Verilog renaming shouldn't result in multiple renames, but found '${c.main} -> $x'")
+      case None =>
+        c.main
+    }
+
+    // Apply all updates
+    c.copy(modules = modulesxx, main = mainx)
+  }
+
+  /** Fix any Verilog keyword name collisions in a [[CircuitState]] while propagating renames
+    * @param state the [[CircuitState]] with possible name collisions
+    * @return a [[CircuitState]] without name collisions
+    */
+  def execute(state: CircuitState): CircuitState = {
+    val renames = RenameMap()
+    renames.setCircuit(state.circuit.main)
+    state.copy(circuit = run(state.circuit, renames), renames = Some(renames))
+  }
 }
 
 /** Makes changes to the Firrtl AST to make Verilog emission easier
diff --git a/src/test/scala/firrtlTests/VerilogEmitterTests.scala b/src/test/scala/firrtlTests/VerilogEmitterTests.scala
index b5ad2f1a..5bd17ac9 100644
--- a/src/test/scala/firrtlTests/VerilogEmitterTests.scala
+++ b/src/test/scala/firrtlTests/VerilogEmitterTests.scala
@@ -232,6 +232,43 @@ class VerilogEmitterSpec extends FirrtlFlatSpec {
     }
   }
 
+  "Verilog name conflicts" should "be resolved" in {
+    val input =
+      """|circuit parameter:
+         |  module parameter:
+         |    input always: UInt<1>
+         |    output always$: UInt<1>
+         |    inst assign of endmodule
+         |    node always_ = not(always)
+         |    node always__ = and(always_, assign.fork)
+         |    always$ <= always__
+         |  module endmodule:
+         |    output fork: UInt<1>
+         |    node const = add(UInt<4>("h1"), UInt<3>("h2"))
+         |    fork <= const
+         |""".stripMargin
+    val check_firrtl =
+      """|circuit parameter_:
+         |  module parameter_:
+         |    input always___: UInt<1>
+         |    output always$: UInt<1>
+         |    inst assign_ of endmodule_
+         |    node always_ = not(always___)
+         |    node always__ = and(always_, assign_.fork_)
+         |    always$ <= always__
+         |  module endmodule_:
+         |    output fork_: UInt<1>
+         |    node const_ = add(UInt<4>("h1"), UInt<3>("h2"))
+         |    fork_ <= const_
+         |""".stripMargin
+    val state = CircuitState(parse(input), UnknownForm, Seq.empty, None)
+    val output = Seq( ToWorkingIR, ResolveKinds, InferTypes, VerilogRename )
+      .foldLeft(state){ case (c, tx) => tx.runTransform(c) }
+    Seq( CheckHighForm )
+      .foldLeft(output.circuit){ case (c, tx) => tx.run(c) }
+    output.circuit.serialize should be (parse(check_firrtl).serialize)
+  }
+
 }
 
 class VerilogDescriptionEmitterSpec extends FirrtlFlatSpec {