Implement MFC-style source locator compression (#2212)

* Implement MFC-style source locator compression

* Fix formatting issues

* Fix emitting empty FileInfo if the firrtl doesn't have one

* Remove '.scala' requirement in FileInfo parsing regex

* Handle parsing of FileInfos with no line/col nums

* Split FileInfos only if they match

This should fix any issues with FileInfos that do not use the "file line:col"
format, and allow any valid firrtl using these info comments to compile.

* Add unit tests for locator compression

* Move InfoTests to InfoSpec class

* Fix existing unit tests with fileinfo comments

* Add unit tests to ignore the algorithm's own output

3 files changed, 179 insertions, 6 deletions

diff --git a/src/main/scala/firrtl/ir/IR.scala b/src/main/scala/firrtl/ir/IR.scala
index 13ba3d46..8ba29d8e 100644
--- a/src/main/scala/firrtl/ir/IR.scala
+++ b/src/main/scala/firrtl/ir/IR.scala
@@ -35,6 +35,7 @@ case class FileInfo(escaped: String) extends Info {
   override def toString: String = " @[" + escaped + "]"
   def ++(that: Info): Info = if (that == NoInfo) this else MultiInfo(Seq(this, that))
   def unescaped: String = FileInfo.unescape(escaped)
+  def split:     (String, String, String) = FileInfo.split(escaped)
   @deprecated("Use FileInfo.unescaped instead. FileInfo.info will be removed in FIRRTL 1.5.", "FIRRTL 1.4")
   def info: StringLit = StringLit(this.unescaped)
 }
@@ -88,6 +89,17 @@ object FileInfo {
     JavaUnicodeEscaper.outsideOf(32, 0x7f)
   )
 
+  // Splits the FileInfo into its corresponding file, line, and column strings
+  private def split(s: String): (String, String, String) = {
+    s match {
+      // Yield the three
+      case FileInfoRegex(file, line, col) => (file, line, col)
+      // Otherwise, just return the string itself and null for the other values
+      case _ => (s, null, null)
+    }
+  }
+
+  private val FileInfoRegex = """(?:([^\s]+)(?: (\d+)\:(\d+)))""".r
 }
 
 case class MultiInfo(infos: Seq[Info]) extends Info {
@@ -102,7 +114,7 @@ case class MultiInfo(infos: Seq[Info]) extends Info {
     else ""
   }
   def ++(that: Info): Info = if (that == NoInfo) this else MultiInfo(infos :+ that)
-  def flatten: Seq[FileInfo] = MultiInfo.flattenInfo(infos)
+  def flatten: Seq[FileInfo] = MultiInfo.compressInfo(MultiInfo.flattenInfo(infos))
 }
 object MultiInfo {
   def apply(infos: Info*) = {
@@ -126,6 +138,100 @@ object MultiInfo {
     case f: FileInfo => Seq(f)
     case MultiInfo(infos) => flattenInfo(infos)
   }
+
+  private def compressInfo(infos: Seq[FileInfo]): Seq[FileInfo] = {
+    // Sort infos by file name, then line number, then column number
+    val sorted = infos.sortWith((A, B) => {
+      val (fileA, lineA, colA) = A.split
+      val (fileB, lineB, colB) = B.split
+
+      // A FileInfo with no line nor column number should be sorted to the beginning of
+      // the sequence of FileInfos that share its fileName. This way, they can be immediately
+      // skipped by the algorithm
+      if (lineA == null || lineB == null)
+        fileA <= fileB && lineA == null
+      else
+        // Default comparison
+        fileA <= fileB &&
+        lineA <= lineB &&
+        colA <= colB
+    })
+
+    // Holds the current file/line being parsed.
+    var currentFile = ""
+    var currentLine = ""
+
+    // Holds any compressed line/column numbers to be appended after the file name
+    var locators = new StringBuilder
+    // Holds all encountered columns that exist within the current line
+    var columns: Seq[String] = Seq()
+
+    var out: Seq[FileInfo] = Seq()
+
+    // Helper function to append the contents of the columns Seq to the locators buffer.
+    def serializeColumns: Unit = {
+      if (columns.size == 0)
+        return
+
+      var columnsList = columns.mkString(",")
+      // Wrap the columns in curly braces if it contains more than one entry
+      if (columns.size > 1)
+        columnsList = '{' + columnsList + '}'
+
+      // If there already exists line/column numbers in the buffer, delimit the new
+      // info with a space
+      if (locators.nonEmpty)
+        locators ++= " "
+
+      locators ++= s"$currentLine:$columnsList"
+    }
+
+    for (info <- sorted) {
+      val (file, line, col) = info.split
+
+      // Only process file infos that match the pattern *fully*, so that all 3 capture groups were
+      // matched
+      // TODO: Enforce a specific format for FileInfos (file.name line1:{col1,col2} line2:{col3,col4}...),
+      // so that this code can run with the assumption that all FileInfos obey that format.
+      if (line != null && col != null) {
+        // If we encounter a new file, yield the current compressed info
+        if (file != currentFile) {
+          if (currentFile.nonEmpty) {
+            serializeColumns
+            out :+= FileInfo.fromEscaped(s"$currentFile $locators")
+          }
+
+          // Reset all tracking variables to now track the new file
+          currentFile = file
+          currentLine = ""
+          locators.clear()
+          columns = Seq()
+        }
+
+        // If we encounter a new line, append the current columns to the line buffer.
+        if (line != currentLine) {
+          if (currentLine.nonEmpty)
+            serializeColumns
+          // Track the new current line
+          currentLine = line
+          columns = Seq()
+        }
+
+        columns :+= col
+      } else
+        // Add in the uncompressed FileInfo
+        out :+= info
+    }
+
+    // Serialize any remaining column info that was parsed by the loop
+    serializeColumns
+
+    // Append the remaining FileInfo if one was parsed
+    if (currentFile.nonEmpty)
+      out :+= FileInfo.fromEscaped(s"$currentFile $locators")
+
+    out
+  }
 }
 
 trait HasName {
diff --git a/src/test/scala/firrtlTests/InfoSpec.scala b/src/test/scala/firrtlTests/InfoSpec.scala
index 43fb6ee1..85b4efac 100644
--- a/src/test/scala/firrtlTests/InfoSpec.scala
+++ b/src/test/scala/firrtlTests/InfoSpec.scala
@@ -166,11 +166,11 @@ class InfoSpec extends FirrtlFlatSpec with FirrtlMatchers {
       """.stripMargin
 
     val result = (new LowFirrtlCompiler).compileAndEmit(CircuitState(parse(input), ChirrtlForm), List.empty)
-    result should containLine("node _GEN_0 = mux(_T_14, _T_16, x) @[GCD.scala 17:18 GCD.scala 17:22 GCD.scala 15:14]")
-    result should containLine("node _GEN_2 = mux(io_e, io_a, _GEN_0) @[GCD.scala 19:15 GCD.scala 19:19]")
+    result should containLine("node _GEN_0 = mux(_T_14, _T_16, x) @[GCD.scala 15:14 17:{18,22}]")
+    result should containLine("node _GEN_2 = mux(io_e, io_a, _GEN_0) @[GCD.scala 19:{15,19}]")
     result should containLine("x <= _GEN_2")
-    result should containLine("node _GEN_1 = mux(_T_18, _T_20, y) @[GCD.scala 18:18 GCD.scala 18:22 GCD.scala 16:14]")
-    result should containLine("node _GEN_3 = mux(io_e, io_b, _GEN_1) @[GCD.scala 19:15 GCD.scala 19:30]")
+    result should containLine("node _GEN_1 = mux(_T_18, _T_20, y) @[GCD.scala 16:14 18:{18,22}]")
+    result should containLine("node _GEN_3 = mux(io_e, io_b, _GEN_1) @[GCD.scala 19:{15,30}]")
     result should containLine("y <= _GEN_3")
   }
 
@@ -254,4 +254,71 @@ class InfoSpec extends FirrtlFlatSpec with FirrtlMatchers {
     parseInfo("test[\\][\\]test").unescaped should be("test[][]test")
   }
 
+  it should "be compressed in Verilog whenever possible" in {
+    def result(info1: String, info2: String, info3: String) = compileBody(
+      s"""output out:UInt<32>
+         |input b:UInt<32>
+         |input c:UInt<1>
+         |input d:UInt<32>
+         |wire a:UInt<32>
+         |when c : @[$info1]
+         |  a <= b @[$info2]
+         |else :
+         |  a <= d @[$info3]
+         |out <= add(a,a)""".stripMargin
+    )
+
+    // Keep different file infos separated
+    result("A 1:1", "B 1:1", "C 1:1") should containLine("  wire [31:0] a = c ? b : d; // @[A 1:1 B 1:1 C 1:1]")
+    // Compress only 2 FileInfos of the same file
+    result("A 1:1", "A 2:3", "C 1:1") should containLine("  wire [31:0] a = c ? b : d; // @[A 1:1 2:3 C 1:1]")
+    // Conmpress 3 lines from the same file into one single FileInfo
+    result("A 1:2", "A 2:4", "A 3:6") should containLine("  wire [31:0] a = c ? b : d; // @[A 1:2 2:4 3:6]")
+    // Compress two columns from the same line, and one different line into one FileInfo
+    result("A 1:2", "A 1:4", "A 2:3") should containLine("  wire [31:0] a = c ? b : d; // @[A 1:{2,4} 2:3]")
+    // Compress three (or more...) columns from the same line into one FileInfo
+    result("A 1:2", "A 1:3", "A 1:4") should containLine("  wire [31:0] a = c ? b : d; // @[A 1:{2,3,4}]")
+
+    // Ignore already-compressed MultiInfos - for when someone may serialize a module first and compile the parsed firrtl into Verilog
+    result("A 1:{2,3,4}", "", "") should containLine(
+      "  wire [31:0] a = c ? b : d; // @[A 1:{2,3,4}]"
+    )
+    // Merge additional FileInfos together, but ignore compressed MultiInfos if they are present
+    result("A 1:{2,3,4}", "B 2:3", "B 4:5") should containLine(
+      "  wire [31:0] a = c ? b : d; // @[A 1:{2,3,4} B 2:3 4:5]"
+    )
+    result("A 2:3", "B 1:{2,3,4}", "C 4:5") should containLine(
+      "  wire [31:0] a = c ? b : d; // @[B 1:{2,3,4} A 2:3 C 4:5]"
+    )
+  }
+
+  it should "not be compressed if it has a non-conforming format" in {
+    // Sample module from the firrtl spec for file info comments
+    val result = compileBody(
+      """output out:UInt @["myfile.txt: 16, 3"]
+        |input b:UInt<32> @["myfile.txt: 17, 3"]
+        |input c:UInt<1> @["myfile.txt: 18, 3"]
+        |input d:UInt<16> @["myfile.txt: 19, 3"]
+        |wire a:UInt @["myfile.txt: 21, 8"]
+        |when c : @["myfile.txt: 24, 8"]
+        |  a <= b @["myfile.txt: 27, 16"]
+        |else :
+        |  a <= d @["myfile.txt: 29, 17"]
+        |out <= add(a,a) @["myfile.txt: 34, 4"]
+        |""".stripMargin
+    )
+
+    // Should compile to the following lines in the test module
+    val check = Seq(
+      """  output [32:0] out, // @[\"myfile.txt: 16, 3\"]""",
+      """  input  [31:0] b, // @[\"myfile.txt: 17, 3\"]""",
+      """  input         c, // @[\"myfile.txt: 18, 3\"]""",
+      """  input  [15:0] d // @[\"myfile.txt: 19, 3\"]""",
+      """  wire [31:0] a = c ? b : {{16'd0}, d}; // @[\"myfile.txt: 24, 8\" \"myfile.txt: 27, 16\" \"myfile.txt: 29, 17\"]""",
+      """  assign out = a + a; // @[\"myfile.txt: 34, 4\"]"""
+    )
+
+    for (line <- check)
+      result should containLine(line)
+  }
 }
diff --git a/src/test/scala/firrtlTests/InlineBooleanExpressionsSpec.scala b/src/test/scala/firrtlTests/InlineBooleanExpressionsSpec.scala
index e11c4281..a1f272c9 100644
--- a/src/test/scala/firrtlTests/InlineBooleanExpressionsSpec.scala
+++ b/src/test/scala/firrtlTests/InlineBooleanExpressionsSpec.scala
@@ -166,7 +166,7 @@ class InlineBooleanExpressionsSpec extends FirrtlFlatSpec {
         |    node _c = in_1 @[A 1:1]
         |    node _t = in_2 @[A 1:1]
         |    node _f = in_3 @[A 1:1]
-        |    out <= mux(in_1, in_2, in_3) @[A 1:1 A 2:2 A 3:3]""".stripMargin
+        |    out <= mux(in_1, in_2, in_3) @[A 1:1 2:2 3:3]""".stripMargin
     val result = exec(input)
     (result) should be(parse(check).serialize)
   }