Add Utils.expandPrefixes as Prefix Unique helper (#900)

This adds a utility, expandPrefixes, that expands a string into all
possible prefixes based on a delimiter. Any repeated occurrence of the
delimiter is viewed as a contributing to a prefix. E.g., "foo_bar" expands
to Seq("foo_", "foo_bar"). This is useful for inlining and keyword
mangling on LowForm. You would like to be able to generate a new name that
is prefix unique with respect to a namespace.

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

2 files changed, 43 insertions, 0 deletions

diff --git a/src/main/scala/firrtl/Utils.scala b/src/main/scala/firrtl/Utils.scala
index dfb635c2..32893411 100644
--- a/src/main/scala/firrtl/Utils.scala
+++ b/src/main/scala/firrtl/Utils.scala
@@ -9,6 +9,7 @@ import firrtl.WrappedExpression._
 import firrtl.WrappedType._
 import scala.collection.mutable
 import scala.collection.mutable.{StringBuilder, ArrayBuffer, LinkedHashMap, HashMap, HashSet}
+import scala.util.matching.Regex
 import java.io.PrintWriter
 import logger.LazyLogging
 
@@ -691,6 +692,22 @@ object Utils extends LazyLogging {
     "SYNTHESIS",
     "PRINTF_COND",
     "VCS")
+
+  /** Expand a name into its prefixes, e.g., 'foo_bar__baz' becomes 'Seq[foo_, foo_bar__, foo_bar__baz]'. This can be used
+    * to produce better names when generating prefix unique names.
+    * @param name a signal name
+    * @param prefixDelim a prefix delimiter (default is "_")
+    * @return the signal name and any prefixes
+    */
+  def expandPrefixes(name: String, prefixDelim: String = "_"): Seq[String] = {
+    val regex = ("(" + Regex.quote(prefixDelim) + ")+[A-Za-z0-9$]").r
+
+    name +: regex
+      .findAllMatchIn(name)
+      .map(_.end - 1)
+      .toSeq
+      .foldLeft(Seq[String]()){ case (seq, id) => seq :+ name.splitAt(id)._1 }
+  }
 }
 
 object MemoizedHash {
diff --git a/src/test/scala/firrtlTests/UtilsSpec.scala b/src/test/scala/firrtlTests/UtilsSpec.scala
new file mode 100644
index 00000000..a1a72634
--- /dev/null
+++ b/src/test/scala/firrtlTests/UtilsSpec.scala
@@ -0,0 +1,26 @@
+package firrtlTests
+
+import org.scalatest.FlatSpec
+import org.scalatest.Matchers._
+
+import firrtl.Utils
+
+class UtilsSpec extends FlatSpec {
+
+  behavior of "Utils.expandPrefix"
+
+  val expandPrefixTests = List(
+    ("return a name without prefixes", "_", "foo", Set("foo")),
+    ("expand a name ending with prefixes", "_", "foo__", Set("foo__")),
+    ("expand a name with on prefix", "_", "foo_bar", Set("foo_bar", "foo_")),
+    ("expand a name with complex prefixes", "_",
+     "foo__$ba9_9X__$$$$$_", Set("foo__$ba9_9X__$$$$$_", "foo__$ba9_9X__", "foo__$ba9_", "foo__")),
+    ("expand a name starting with a delimiter", "_", "__foo_bar", Set("__", "__foo_", "__foo_bar")),
+    ("expand a name with a $ delimiter", "$", "foo$bar$$$baz", Set("foo$", "foo$bar$$$", "foo$bar$$$baz")),
+    ("expand a name with a multi-character delimiter", "FOO", "fooFOOFOOFOObar", Set("fooFOOFOOFOO", "fooFOOFOOFOObar"))
+  )
+
+  for ((description, delimiter, in, out) <- expandPrefixTests) {
+    it should description in { Utils.expandPrefixes(in, delimiter).toSet should be (out)}
+  }
+}