Fix renaming of annotations with paths (#967)

* check isLocal before removing target tokens in RenameMap

* add fix for Adam's test case, add more test cases

* fix multiple renaming bug

* call componentGet before checking underlying for ReferenceTargets in recursiveGet

* add ModuleGet that implements new instance rename order

* normalize target before renaming

* fix forall/exists bug

* add guards for isLocal cases

* fix circuit renaming, fix traverseHierarchy, add debug prints

* remove sensitivity stuff

* add more tests

* reapply parent path to renamed subpath, fix reference -> instance renames

* remove debug prints

* add instance as reference test case

* fix Ref->IsMod, IsMod->Ref renamed, fix extra test cases

* fix ofModule renaming for refs/instances

* fix renaming of ofModules, change tests

* fix more InstanceTarget rename bugs

* remove bad ReferenceTarget test case

* cleanup midRename of recursiveGet

* fix comments

* fix multiple ModuleTarget renames for InstanceTargets

* dis-allow renaming of ModuleTargets to References

* add back removed lines in RemoveCHIRRTL

* fix indents

* only add ofModule to refs if renaming an inst as a ref

* change .moduleOpt.get to .module

* disallow renaming ReferenceTarget->ModuleTarget

* disallow ref->mod renames in tests, add inst as ref test cases

* cache results of get functions

* fix bot/mid/top renames, add andThen

* fix andThen, add test case

* add more test cases, fix ++

* fix comments, make things private

* dont quit if earlier returns None, add dedup/inline rename tests

* don't rename OfModules to instances paths

* update dedup test

* don't treat references as instances, don't reapply parents to absolute paths

* fix more test cases

* short-circuit OfModule renames if an absolute path is found

* update andThen, remove orElse, deprecate ++

* removed commented code

* update comments

* respond to comments

3 files changed, 696 insertions, 141 deletions

diff --git a/src/main/scala/firrtl/RenameMap.scala b/src/main/scala/firrtl/RenameMap.scala
index 7b0388bc..30ad5a2f 100644
--- a/src/main/scala/firrtl/RenameMap.scala
+++ b/src/main/scala/firrtl/RenameMap.scala
@@ -4,7 +4,7 @@ package firrtl
 
 import annotations._
 import firrtl.RenameMap.{CircularRenameException, IllegalRenameException}
-import firrtl.annotations.TargetToken.{Field, Index}
+import firrtl.annotations.TargetToken.{Field, Index, Instance, OfModule}
 
 import scala.collection.mutable
 
@@ -35,7 +35,12 @@ object RenameMap {
   * These are mutable datastructures for convenience
   */
 // TODO This should probably be refactored into immutable and mutable versions
-final class RenameMap private () {
+final class RenameMap private (val underlying: mutable.HashMap[CompleteTarget, Seq[CompleteTarget]] = mutable.HashMap[CompleteTarget, Seq[CompleteTarget]](), val chained: Option[RenameMap] = None) {
+
+  /** Chain a [[RenameMap]] with this [[RenameMap]]
+    * @param next the map to chain with this map
+    */
+  def andThen(next: RenameMap) = new RenameMap(next.underlying, chained = Some(this))
 
   /** Record that the from [[firrtl.annotations.CircuitTarget CircuitTarget]] is renamed to another
     * [[firrtl.annotations.CircuitTarget CircuitTarget]]
@@ -113,7 +118,23 @@ final class RenameMap private () {
     * @param renameMap
     * @return
     */
-  def ++ (renameMap: RenameMap): RenameMap = RenameMap(underlying ++ renameMap.getUnderlying)
+  @deprecated("will be removed in 1.3", "1.2")
+  def ++ (renameMap: RenameMap): RenameMap = {
+    val newChained = if (chained.nonEmpty && renameMap.chained.nonEmpty) {
+      Some(chained.get ++ renameMap.chained.get)
+    } else {
+      chained.map(_.copy())
+    }
+    new RenameMap(underlying = underlying ++ renameMap.getUnderlying, chained = newChained)
+  }
+
+  /** Creates a deep copy of this [[RenameMap]]
+    */
+  def copy(chained: Option[RenameMap] = chained): RenameMap = {
+    val ret = new RenameMap(chained = chained.map(_.copy()))
+    ret.recordAll(underlying)
+    ret
+  }
 
   /** Returns the underlying map of rename information
     * @return
@@ -142,11 +163,6 @@ final class RenameMap private () {
     k.serialize + "=>" + v.map(_.serialize).mkString(", ")
   }.mkString("\n")
 
-  /** Maps old names to new names. New names could still require renaming parts of their name
-    * Old names must refer to existing names in the old circuit
-    */
-  private val underlying = mutable.HashMap[CompleteTarget, Seq[CompleteTarget]]()
-
   /** Records which local InstanceTargets will require modification.
     * Used to reduce time to rename nonlocal targets who's path does not require renaming
     */
@@ -156,6 +172,13 @@ final class RenameMap private () {
     */
   private val getCache = mutable.HashMap[CompleteTarget, Seq[CompleteTarget]]()
 
+  /** Caches results of referenceGet. Is cleared any time a new rename target is added
+    */
+  private val traverseTokensCache = mutable.HashMap[ReferenceTarget, Option[Seq[IsComponent]]]()
+  private val traverseHierarchyCache = mutable.HashMap[ReferenceTarget, Option[Seq[IsComponent]]]()
+  private val traverseLeftCache = mutable.HashMap[InstanceTarget, Option[Seq[IsModule]]]()
+  private val traverseRightCache = mutable.HashMap[InstanceTarget, Seq[IsModule]]()
+
   /** Updates [[sensitivity]]
     * @param from original target
     * @param to new target
@@ -176,140 +199,283 @@ final class RenameMap private () {
     * @return Optionally return sequence of targets that key remaps to
     */
   private def completeGet(key: CompleteTarget): Option[Seq[CompleteTarget]] = {
+    if (chained.nonEmpty) {
+      val chainedRet = chained.get.completeGet(key).getOrElse(Seq(key))
+      if (chainedRet.isEmpty) {
+        Some(chainedRet)
+      } else {
+        val hereRet = chainedRet.flatMap(hereCompleteGet)
+        if (hereRet.isEmpty) { None } else { Some(hereRet.flatten) }
+      }
+    } else {
+      hereCompleteGet(key)
+    }
+  }
+
+  private def hereCompleteGet(key: CompleteTarget): Option[Seq[CompleteTarget]] = {
     val errors = mutable.ArrayBuffer[String]()
     val ret = if(hasChanges) {
-      val ret = recursiveGet(mutable.LinkedHashSet.empty[CompleteTarget], errors)(key)
+      val ret = recursiveGet(errors)(key)
       if(errors.nonEmpty) { throw IllegalRenameException(errors.mkString("\n")) }
       if(ret.size == 1 && ret.head == key) { None } else { Some(ret) }
     } else { None }
     ret
   }
 
-  // scalastyle:off
-  // This function requires a large cyclomatic complexity, and is best naturally expressed as a large function
+
+  /** Checks for renames of only the component portion of a [[ReferenceTarget]]
+    * Recursively checks parent [[ReferenceTarget]]s until a match is found
+    * Parents with longer paths/components are checked first. longer paths take
+    * priority over longer components.
+    *
+    * For example, the order that targets are checked for ~Top|Top/a:A/b:B/c:C>f.g is:
+    * ~Top|Top/a:A/b:B/c:C>f.g
+    * ~Top|Top/a:A/b:B/c:C>f
+    * ~Top|A/b:B/c:C>f.g
+    * ~Top|A/b:B/c:C>f
+    * ~Top|B/c:C>f.g
+    * ~Top|B/c:C>f
+    * ~Top|C>f.g
+    * ~Top|C>f
+    *
+    * @param errors Used to record illegal renames
+    * @param key Target to rename
+    * @return Renamed targets if a match is found, otherwise None
+    */
+  private def referenceGet(errors: mutable.ArrayBuffer[String])(key: ReferenceTarget): Option[Seq[IsComponent]] = {
+    def traverseTokens(key: ReferenceTarget): Option[Seq[IsComponent]] = traverseTokensCache.getOrElseUpdate(key, {
+      if (underlying.contains(key)) {
+        Some(underlying(key).flatMap {
+          case comp: IsComponent => Some(comp)
+          case other =>
+            errors += s"reference ${key.targetParent} cannot be renamed to a non-component ${other}"
+            None
+        })
+      } else {
+        key match {
+          case t: ReferenceTarget if t.component.nonEmpty =>
+            val last = t.component.last
+            val parent = t.copy(component = t.component.dropRight(1))
+            traverseTokens(parent).map(_.flatMap { x =>
+              (x, last) match {
+                case (t2: InstanceTarget, Field(f)) => Some(t2.ref(f))
+                case (t2: ReferenceTarget, Field(f)) => Some(t2.field(f))
+                case (t2: ReferenceTarget, Index(i)) => Some(t2.index(i))
+                case other =>
+                  errors += s"Illegal rename: ${key.targetParent} cannot be renamed to ${other._1} - must rename $key directly"
+                  None
+              }
+            })
+          case t: ReferenceTarget => None
+        }
+      }
+    })
+
+    def traverseHierarchy(key: ReferenceTarget): Option[Seq[IsComponent]] = traverseHierarchyCache.getOrElseUpdate(key, {
+      val tokenRenamed = traverseTokens(key)
+      if (tokenRenamed.nonEmpty) {
+        tokenRenamed
+      } else {
+        key match {
+          case t: ReferenceTarget if t.isLocal => None
+          case t: ReferenceTarget =>
+            val encapsulatingInstance = t.path.head._1.value
+            val stripped = t.stripHierarchy(1)
+            traverseHierarchy(stripped).map(_.map {
+              _.addHierarchy(t.module, encapsulatingInstance)
+            })
+        }
+      }
+    })
+
+    traverseHierarchy(key)
+  }
+
+  /** Checks for renames of only the path portion of an [[InstanceTarget]]
+    * Recursively checks parent [[IsModule]]s until a match is found
+    * First checks all parent paths from longest to shortest. Then
+    * recursively checks paths leading to the encapsulating module.
+    * Stops on the first match found.
+    *
+    * For example, the order that targets are checked for ~Top|Top/a:A/b:B/c:C is:
+    * ~Top|Top/a:A/b:B/c:C
+    * ~Top|A/b:B/c:C
+    * ~Top|B/c:C
+    * ~Top|Top/a:A/b:B
+    * ~Top|A/b:B
+    * ~Top|Top/a:A
+    *
+    * @param errors Used to record illegal renames
+    * @param key Target to rename
+    * @return Renamed targets, contains only the original target if none are found
+    */
+  private def instanceGet(errors: mutable.ArrayBuffer[String])(key: InstanceTarget): Seq[IsModule] = {
+    def traverseLeft(key: InstanceTarget): Option[Seq[IsModule]] = traverseLeftCache.getOrElseUpdate(key, {
+      val getOpt = underlying.get(key)
+
+      if (getOpt.nonEmpty) {
+        getOpt.map(_.flatMap {
+          case isMod: IsModule => Some(isMod)
+          case other =>
+            errors += s"IsModule: $key cannot be renamed to non-IsModule $other"
+            None
+        })
+      } else {
+        key match {
+          case t: InstanceTarget if t.isLocal => None
+          case t: InstanceTarget =>
+            val (Instance(outerInst), OfModule(outerMod)) = t.path.head
+            val stripped = t.copy(path = t.path.tail, module = outerMod)
+            traverseLeft(stripped).map(_.map {
+              case absolute if absolute.path.nonEmpty && absolute.circuit == absolute.path.head._2.value => absolute
+              case relative => relative.addHierarchy(t.module, outerInst)
+            })
+        }
+      }
+    })
+
+    def traverseRight(key: InstanceTarget): Seq[IsModule] = traverseRightCache.getOrElseUpdate(key, {
+      val findLeft = traverseLeft(key)
+      if (findLeft.nonEmpty) {
+        findLeft.get
+      } else {
+        key match {
+          case t: InstanceTarget if t.isLocal => Seq(key)
+          case t: InstanceTarget =>
+            val (Instance(i), OfModule(m)) = t.path.last
+            val parent = t.copy(path = t.path.dropRight(1), instance = i, ofModule = m)
+            traverseRight(parent).map(_.instOf(t.instance, t.ofModule))
+        }
+      }
+    })
+
+    traverseRight(key)
+  }
+
+  private def circuitGet(errors: mutable.ArrayBuffer[String])(key: CircuitTarget): Seq[CircuitTarget] = {
+    underlying.get(key).map(_.flatMap {
+      case c: CircuitTarget => Some(c)
+      case other =>
+        errors += s"Illegal rename: $key cannot be renamed to non-circuit target: $other"
+        None
+    }).getOrElse(Seq(key))
+  }
+
+  private def moduleGet(errors: mutable.ArrayBuffer[String])(key: ModuleTarget): Seq[IsModule] = {
+    underlying.get(key).map(_.flatMap {
+      case mod: IsModule => Some(mod)
+      case other =>
+        errors += s"Illegal rename: $key cannot be renamed to non-module target: $other"
+        None
+    }).getOrElse(Seq(key))
+  }
+
   /** Recursively renames a target so the returned targets are complete renamed
-    * @param set Used to detect circular renames
     * @param errors Used to record illegal renames
     * @param key Target to rename
     * @return Renamed targets
     */
-  private def recursiveGet(set: mutable.LinkedHashSet[CompleteTarget],
-                           errors: mutable.ArrayBuffer[String]
-                          )(key: CompleteTarget): Seq[CompleteTarget] = {
+  private def recursiveGet(errors: mutable.ArrayBuffer[String])(key: CompleteTarget): Seq[CompleteTarget] = {
     if(getCache.contains(key)) {
       getCache(key)
     } else {
-      // First, check if whole key is remapped
-      // Note that remapped could hold stale parent targets that require renaming
-      val remapped = underlying.getOrElse(key, Seq(key))
-
-      // If we've seen this key before in recursive calls to parentTargets, then we know a circular renaming
-      // mapping has occurred, and no legal name exists
-      if(set.contains(key) && !key.isInstanceOf[CircuitTarget]) {
-        throw CircularRenameException(s"Illegal rename: circular renaming is illegal - ${set.mkString(" -> ")}")
-      }
-
-      // Add key to set to detect circular renaming
-      set += key
-
-      // Curry recursiveGet for cleaner syntax below
-      val getter = recursiveGet(set, errors)(_)
+      val getter = recursiveGet(errors)(_)
 
-      // For each remapped key, call recursiveGet on their parentTargets
-      val ret = remapped.flatMap {
-
-        // If t is a CircuitTarget, return it because it has no parent target
+      // rename just the first level e.g. just rename component/path portion for ReferenceTargets
+      val topRename = key match {
         case t: CircuitTarget => Seq(t)
+        case t: ModuleTarget => Seq(t)
+        case t: InstanceTarget => instanceGet(errors)(t)
+        case ref: ReferenceTarget if ref.isLocal => referenceGet(errors)(ref).getOrElse(Seq(ref))
+        case ref @ ReferenceTarget(c, m, p, r, t) =>
+          val (Instance(inst), OfModule(ofMod)) = p.last
+          referenceGet(errors)(ref).getOrElse {
+            val parent = InstanceTarget(c, m, p.dropRight(1), inst, ofMod)
+            instanceGet(errors)(parent).map(ref.setPathTarget(_))
+          }
+      }
 
-        // If t is a ModuleTarget, try to rename parent target, then update t's parent
-        case t: ModuleTarget => getter(t.targetParent).map {
-          case CircuitTarget(c) => ModuleTarget(c, t.module)
-        }
-
-        /** If t is an InstanceTarget (has a path) but has no references:
-          * 1) Check whether the instance has been renamed (asReference)
-          * 2) Check whether the ofModule of the instance has been renamed (only 1:1 renaming is ok)
-          */
-        case t: InstanceTarget =>
-          getter(t.asReference).map {
-            case t2:InstanceTarget => t2
-            case t2@ReferenceTarget(c, m, p, r, Nil) =>
-              val t3 = InstanceTarget(c, m, p, r, t.ofModule)
-              val ofModuleTarget = t3.ofModuleTarget
-              getter(ofModuleTarget) match {
-                case Seq(ModuleTarget(newCircuit, newOf)) if newCircuit == t3.circuit => t3.copy(ofModule = newOf)
+      // rename the next level up
+      val midRename = topRename.flatMap {
+        case t: CircuitTarget => Seq(t)
+        case t: ModuleTarget => moduleGet(errors)(t)
+        case t: IsComponent =>
+          // rename all modules on the path
+          val renamedPath = t.asPath.reverse.foldLeft((Option.empty[IsModule], Seq.empty[(Instance, OfModule)])) {
+            case (absolute@ (Some(_), _), _) => absolute
+            case ((None, children), pair) =>
+              val pathMod = ModuleTarget(t.circuit, pair._2.value)
+              moduleGet(errors)(pathMod) match {
+                case Seq(absolute: IsModule) if absolute.circuit == t.circuit && absolute.module == t.circuit =>
+                  val withChildren = children.foldLeft(absolute) {
+                    case (target, (inst, ofMod)) => target.instOf(inst.value, ofMod.value)
+                  }
+                  (Some(withChildren), children)
+                case Seq(isMod: ModuleTarget) if isMod.circuit == t.circuit =>
+                  (None, pair.copy(_2 = OfModule(isMod.module)) +: children)
+                case Seq(isMod: InstanceTarget) if isMod.circuit == t.circuit =>
+                  (None, pair +: children)
                 case other =>
-                  errors += s"Illegal rename: ofModule of $t is renamed to $other - must rename $t directly."
-                  t
-              }
-            case other =>
-              errors += s"Illegal rename: $t has new instance reference $other"
-              t
+                  val error = s"ofModule ${pathMod} cannot be renamed to $other " +
+                    "- an ofModule can only be renamed to a single IsModule with the same circuit"
+                  errors += error
+                  (None, pair +: children)
+            }
           }
 
-        /** If t is a ReferenceTarget:
-          * 1) Check parentTarget to tokens
-          * 2) Check ReferenceTarget with one layer stripped from its path hierarchy (i.e. a new root module)
-          */
-        case t: ReferenceTarget =>
-          val ret: Seq[CompleteTarget] = if(t.component.nonEmpty) {
-            val last = t.component.last
-            getter(t.targetParent).map{ x =>
-              (x, last) match {
-                case (t2: ReferenceTarget, Field(f)) => t2.field(f)
-                case (t2: ReferenceTarget, Index(i)) => t2.index(i)
-                case other =>
-                  errors += s"Illegal rename: ${t.targetParent} cannot be renamed to ${other._1} - must rename $t directly"
-                  t
+          renamedPath match {
+            case (Some(absolute), _) =>
+              t match {
+                case ref: ReferenceTarget => Seq(ref.copy(circuit = absolute.circuit, module = absolute.module, path = absolute.asPath))
+                case inst: InstanceTarget => Seq(absolute)
               }
-            }
-          } else {
-            val pathTargets = sensitivity.empty ++ (t.pathAsTargets ++ t.pathAsTargets.map(_.asReference))
-            if(t.pathAsTargets.nonEmpty && sensitivity.intersect(pathTargets).isEmpty) Seq(t) else {
-              getter(t.pathTarget).map {
-                case newPath: IsModule => t.setPathTarget(newPath)
-                case other =>
-                  errors += s"Illegal rename: path ${t.pathTarget} of $t cannot be renamed to $other - must rename $t directly"
-                  t
+            case (_, children) =>
+              // rename the root module and set the new path
+              moduleGet(errors)(ModuleTarget(t.circuit, t.module)).map { mod =>
+                val newPath = mod.asPath ++ children
+
+                t match {
+                  case ref: ReferenceTarget => ref.copy(circuit = mod.circuit, module = mod.module, path = newPath)
+                  case inst: InstanceTarget =>
+                    val (Instance(newInst), OfModule(newOfMod)) = newPath.last
+                    inst.copy(circuit = mod.circuit,
+                      module = mod.module,
+                      path = newPath.dropRight(1),
+                      instance = newInst,
+                      ofModule = newOfMod)
+                }
               }
-            }
           }
-          ret.flatMap {
-            case y: IsComponent if !y.isLocal =>
-              val encapsulatingInstance = y.path.head._1.value
-              getter(y.stripHierarchy(1)).map {
-                _.addHierarchy(y.moduleOpt.get, encapsulatingInstance)
+      }
+
+      // rename the last level
+      val botRename = midRename.flatMap {
+        case t: CircuitTarget => circuitGet(errors)(t)
+        case t: ModuleTarget =>
+          circuitGet(errors)(CircuitTarget(t.circuit)).map {
+            case CircuitTarget(c) => t.copy(circuit = c)
+          }
+        case t: IsComponent =>
+          circuitGet(errors)(CircuitTarget(t.circuit)).map {
+            case CircuitTarget(c) =>
+              t match {
+                case ref: ReferenceTarget => ref.copy(circuit = c)
+                case inst: InstanceTarget => inst.copy(circuit = c)
               }
-            case other => Seq(other)
           }
       }
 
-      // Remove key from set as visiting the same key twice is ok, as long as its not during the same recursive call
-      set -= key
-
       // Cache result
-      getCache(key) = ret
-
-      // Return result
-      ret
-
+      getCache(key) = botRename
+      botRename
     }
   }
-  // scalastyle:on
 
   /** Fully renames from to tos
     * @param from
     * @param tos
     */
   private def completeRename(from: CompleteTarget, tos: Seq[CompleteTarget]): Unit = {
-    def check(from: CompleteTarget, to: CompleteTarget)(t: CompleteTarget): Unit = {
-      require(from != t, s"Cannot record $from to $to, as it is a circular constraint")
-      t match {
-        case _: CircuitTarget =>
-        case other: IsMember => check(from, to)(other.targetParent)
-      }
-    }
-    tos.foreach { to => if(from != to) check(from, to)(to) }
     (from, tos) match {
       case (x, Seq(y)) if x == y =>
       case _ =>
@@ -318,6 +484,10 @@ final class RenameMap private () {
         val updated = existing ++ tos
         underlying(from) = updated
         getCache.clear()
+        traverseTokensCache.clear()
+        traverseHierarchyCache.clear()
+        traverseLeftCache.clear()
+        traverseRightCache.clear()
     }
   }
 
diff --git a/src/main/scala/firrtl/annotations/Target.scala b/src/main/scala/firrtl/annotations/Target.scala
index 72864957..313f1dc2 100644
--- a/src/main/scala/firrtl/annotations/Target.scala
+++ b/src/main/scala/firrtl/annotations/Target.scala
@@ -402,6 +402,8 @@ trait IsModule extends IsMember {
 
   /** @return Creates a new Target, appending an instance and ofmodule */
   def instOf(instance: String, of: String): InstanceTarget
+
+  def addHierarchy(root: String, inst: String): InstanceTarget
 }
 
 /** A component of a FIRRTL Module (e.g. cannot point to a CircuitTarget or ModuleTarget)
diff --git a/src/test/scala/firrtlTests/RenameMapSpec.scala b/src/test/scala/firrtlTests/RenameMapSpec.scala
index b063599b..702f3939 100644
--- a/src/test/scala/firrtlTests/RenameMapSpec.scala
+++ b/src/test/scala/firrtlTests/RenameMapSpec.scala
@@ -4,8 +4,10 @@ package firrtlTests
 
 import firrtl.RenameMap
 import firrtl.FIRRTLException
-import firrtl.RenameMap.{CircularRenameException, IllegalRenameException}
+import firrtl.RenameMap.IllegalRenameException
 import firrtl.annotations._
+import firrtl.annotations.Target
+import firrtl.annotations.TargetToken.{Instance, OfModule}
 
 class RenameMapSpec extends FirrtlFlatSpec {
   val cir   = CircuitTarget("Top")
@@ -111,13 +113,13 @@ class RenameMapSpec extends FirrtlFlatSpec {
   it should "rename targets if instance and module in the path are renamed" in {
     val renames = RenameMap()
     renames.record(Middle, Middle2)
-    renames.record(Top.ref("m"), Top.ref("m2"))
+    renames.record(Top.instOf("m", "Middle"), Top.instOf("m2", "Middle"))
     renames.get(Top_m) should be (Some(Seq(Top.instOf("m2", "Middle2"))))
   }
 
   it should "rename targets if instance in the path are renamed" in {
     val renames = RenameMap()
-    renames.record(Top.ref("m"), Top.ref("m2"))
+    renames.record(Top.instOf("m", "Middle"), Top.instOf("m2", "Middle"))
     renames.get(Top_m) should be (Some(Seq(Top.instOf("m2", "Middle"))))
   }
 
@@ -141,7 +143,7 @@ class RenameMapSpec extends FirrtlFlatSpec {
 
   it should "properly rename if middle is inlined" in {
     val renames = RenameMap()
-    renames.record(Top_m.ref("l"), Top.ref("m_l"))
+    renames.record(Top_m_l, Top.instOf("m_l", "Leaf"))
     renames.get(Top_m_l_a) should be (Some(Seq(Top.instOf("m_l", "Leaf").ref("a"))))
   }
 
@@ -186,35 +188,19 @@ class RenameMapSpec extends FirrtlFlatSpec {
   }
 
   it should "rename instances with same ofModule" in {
-    val Middle_o = Middle.ref("o")
-    val Middle_i = Middle.ref("i")
+    val Middle_o = Middle.instOf("o", "O")
+    val Middle_i = Middle.instOf("i", "O")
     val renames = RenameMap()
     renames.record(Middle_o, Middle_i)
     renames.get(Middle.instOf("o", "O")) should be (Some(Seq(Middle.instOf("i", "O"))))
   }
 
-  it should "detect circular renames" in {
-    case class BadRename(from: IsMember, tos: Seq[IsMember])
-    val badRenames =
-      Seq(
-        BadRename(foo, Seq(foo.field("bar"))),
-        BadRename(modA, Seq(foo))
-        //BadRename(cir, Seq(foo)),
-        //BadRename(cir, Seq(modA))
-      )
-    // Run all BadRename tests
-    for (BadRename(from, tos) <- badRenames) {
-      val fromN = from
-      val tosN = tos.mkString(", ")
-      //it should s"error if a $fromN is renamed to $tosN" in {
-      val renames = RenameMap()
-      for (to <- tos) {
-        a [IllegalArgumentException] shouldBe thrownBy {
-          renames.record(from, to)
-        }
-      }
-      //}
-    }
+  it should "not treat references as instances targets" in {
+    val Middle_o = Middle.ref("o")
+    val Middle_i = Middle.ref("i")
+    val renames = RenameMap()
+    renames.record(Middle_o, Middle_i)
+    renames.get(Middle.instOf("o", "O")) should be (None)
   }
 
   it should "be able to rename weird stuff" in {
@@ -222,8 +208,8 @@ class RenameMapSpec extends FirrtlFlatSpec {
     case class BadRename(from: CompleteTarget, tos: Seq[CompleteTarget])
     val badRenames =
       Seq(//BadRename(foo, Seq(cir)),
-        BadRename(foo, Seq(modB)),
-        BadRename(modA, Seq(fooB)),
+        //BadRename(foo, Seq(modB)),
+        //BadRename(modA, Seq(fooB)),
         //BadRename(modA, Seq(cir)),
         //BadRename(cir, Seq(foo)),
         //BadRename(cir, Seq(modA)),
@@ -248,13 +234,13 @@ class RenameMapSpec extends FirrtlFlatSpec {
     }
   }
 
-  it should "error if a circular rename occurs" in {
+  it should "not error if a circular rename occurs" in {
     val renames = RenameMap()
     val top = CircuitTarget("Top")
     renames.record(top.module("A"), top.module("B").instOf("c", "C"))
     renames.record(top.module("B"), top.module("A").instOf("c", "C"))
-    a [CircularRenameException] shouldBe thrownBy {
-      renames.get(top.module("A"))
+    renames.get(top.module("A")) should be {
+      Some(Seq(top.module("B").instOf("c", "C")))
     }
   }
 
@@ -267,17 +253,18 @@ class RenameMapSpec extends FirrtlFlatSpec {
     renames.get(top.module("B")) should be (Some(Seq(top.module("A"))))
   }
 
-  it should "error if a reference is renamed to a module, and then we try to rename the reference's field" in {
+  it should "error if a reference is renamed to a module and vice versa" in {
     val renames = RenameMap()
     val top = CircuitTarget("Top")
     renames.record(top.module("A").ref("ref"), top.module("B"))
-    renames.get(top.module("A").ref("ref")) should be(Some(Seq(top.module("B"))))
+    renames.record(top.module("C"), top.module("D").ref("ref"))
     a [IllegalRenameException] shouldBe thrownBy {
-      renames.get(top.module("A").ref("ref").field("field"))
+      renames.get(top.module("C"))
     }
     a [IllegalRenameException] shouldBe thrownBy {
-      renames.get(top.module("A").instOf("ref", "R"))
+      renames.get(top.module("A").ref("ref").field("field"))
     }
+    renames.get(top.module("A").instOf("ref", "R")) should be(None)
   }
 
   it should "error if we rename an instance's ofModule into a non-module" in {
@@ -300,4 +287,400 @@ class RenameMapSpec extends FirrtlFlatSpec {
       println(renames.get(top.module("E").instOf("f", "F").ref("g")))
     }
   }
+
+  it should "rename reference targets with paths if their corresponding pathless target are renamed" in {
+    val cir = CircuitTarget("Top")
+    val modTop = cir.module("Top")
+    val modA = cir.module("A")
+
+    val aggregate = modA.ref("agg")
+    val subField1 = aggregate.field("field1")
+    val subField2 = aggregate.field("field2")
+
+    val lowered1 = aggregate.copy(ref = "agg_field1")
+    val lowered2 = aggregate.copy(ref = "agg_field2")
+
+    // simulating LowerTypes transform
+    val renames = RenameMap()
+    renames.record(subField1, lowered1)
+    renames.record(subField2, lowered2)
+    renames.record(aggregate, Seq(lowered1, lowered2))
+
+    val path = modTop.instOf("b", "B").instOf("a", "A")
+    val testRef1 = subField1.setPathTarget(path)
+
+    renames.get(testRef1) should be {
+      Some(Seq(testRef1.copy(ref = "agg_field1", component = Nil)))
+    }
+  }
+
+  // ~Top|Module/i1:I1>foo.field, where rename map contains ~Top|Module/i1:I1>foo -> ~Top|Module/i1:I1>bar.
+  it should "properly rename reference targets with the same paths" in {
+    val cir = CircuitTarget("Top")
+    val modTop = cir.module("Top")
+    val mod = cir.module("Module")
+
+    val path = mod.instOf("i1", "I1")
+    val oldAgg = mod.ref("foo").setPathTarget(path)
+    val newAgg = mod.ref("bar").setPathTarget(path)
+
+    val renames = RenameMap()
+    renames.record(oldAgg, newAgg)
+
+    val testRef = oldAgg.field("field")
+    renames.get(testRef) should be {
+      Some(Seq(newAgg.field("field")))
+    }
+  }
+
+  it should "properly rename reference targets with partially matching paths" in {
+    val cir = CircuitTarget("Top")
+    val modTop = cir.module("Top")
+    val modA = cir.module("A")
+    val modB = cir.module("B")
+
+    val path = modB.instOf("a", "A")
+    val oldRef = modA.ref("oldRef").setPathTarget(path)
+    val newRef = modA.ref("newRef").setPathTarget(path)
+
+    val renames = RenameMap()
+    renames.record(oldRef, newRef)
+
+    val testRef = oldRef.addHierarchy("B", "b")
+    renames.get(testRef) should be {
+      Some(Seq(newRef.addHierarchy("B", "b")))
+    }
+  }
+
+  it should "properly rename reference targets with partially matching paths and partially matching target tokens" in {
+    val cir = CircuitTarget("Top")
+    val modTop = cir.module("Top")
+    val modA = cir.module("A")
+    val modB = cir.module("B")
+
+    val path = modB.instOf("a", "A")
+    val oldAgg = modA.ref("oldAgg").setPathTarget(path).field("field1")
+    val newAgg = modA.ref("newAgg").setPathTarget(path)
+
+    val renames = RenameMap()
+    renames.record(oldAgg, newAgg)
+
+    val testRef = oldAgg.addHierarchy("B", "b").field("field2")
+    renames.get(testRef) should be {
+      Some(Seq(newAgg.addHierarchy("B", "b").field("field2")))
+    }
+  }
+
+  it should "rename targets with multiple renames starting from most specific to least specific" in {
+    val cir = CircuitTarget("Top")
+    val modTop = cir.module("Top")
+    val modA = cir.module("A")
+    val modB = cir.module("B")
+    val modC = cir.module("C")
+
+    // from: ~Top|A/b:B/c:C>ref.f1.f2.f3
+    // to: ~Top|A/b:B/c:C>ref.f1.f2.f333
+    // renamed first because it is an exact match
+    val from1 = modA
+      .instOf("b", "B")
+      .instOf("c", "C")
+      .ref("ref")
+      .field("f1")
+      .field("f2")
+      .field("f3")
+    val to1 = modA
+      .instOf("b", "B")
+      .instOf("c", "C")
+      .ref("ref")
+      .field("f1")
+      .field("f2")
+      .field("f33")
+
+    // from: ~Top|A/b:B/c:C>ref.f1.f2
+    // to: ~Top|A/b:B/c:C>ref.f1
+    // renamed second because it is a parent target
+    val from2 = modA
+      .instOf("b", "B")
+      .instOf("c", "C")
+      .ref("ref")
+      .field("f1")
+      .field("f2")
+    val to2   = modA
+      .instOf("b", "B")
+      .instOf("c", "C")
+      .ref("ref")
+      .field("f1")
+      .field("f22")
+
+    // from: ~Top|B/c:C>ref.f1
+    // to: ~Top|B/c:C>ref.f11
+    // renamed third because it has a smaller hierarchy
+    val from3 = modB
+      .instOf("c", "C")
+      .ref("ref")
+      .field("f1")
+    val to3   = modB
+      .instOf("c", "C")
+      .ref("ref")
+      .field("f11")
+
+    // from: ~Top|C>ref
+    // to: ~Top|C>refref
+    // renamed last because it has no path
+    val from4 = modC.ref("ref")
+    val to4   = modC.ref("refref")
+
+    val renames1 = RenameMap()
+    renames1.record(from1, to1)
+    renames1.record(from2, to2)
+    renames1.record(from3, to3)
+    renames1.record(from4, to4)
+
+    renames1.get(from1) should be {
+      Some(Seq(modA
+        .instOf("b", "B")
+        .instOf("c", "C")
+        .ref("ref")
+        .field("f1")
+        .field("f2")
+        .field("f33")
+      ))
+    }
+
+    val renames2 = RenameMap()
+    renames2.record(from2, to2)
+    renames2.record(from3, to3)
+    renames2.record(from4, to4)
+
+    renames2.get(from1) should be {
+      Some(Seq(modA
+        .instOf("b", "B")
+        .instOf("c", "C")
+        .ref("ref")
+        .field("f1")
+        .field("f22")
+        .field("f3")
+      ))
+    }
+
+    val renames3 = RenameMap()
+    renames3.record(from3, to3)
+    renames3.record(from4, to4)
+
+    renames3.get(from1) should be {
+      Some(Seq(modA
+        .instOf("b", "B")
+        .instOf("c", "C")
+        .ref("ref")
+        .field("f11")
+        .field("f2")
+        .field("f3")
+      ))
+    }
+  }
+
+  it should "correctly handle renaming of modules to instances" in {
+    val cir = CircuitTarget("Top")
+    val renames = RenameMap()
+    val from = cir.module("C")
+    val to = cir.module("D").instOf("e", "E").instOf("f", "F")
+    renames.record(from, to)
+    renames.get(cir.module("C")) should be {
+      Some(Seq(cir.module("D").instOf("e", "E").instOf("f", "F")))
+    }
+    renames.get(cir.module("A").instOf("b", "B").instOf("c", "C")) should be {
+      None
+    }
+  }
+
+  it should "correctly handle renaming of paths and components at the same time" in {
+    val cir = CircuitTarget("Top")
+    val renames = RenameMap()
+    val from = cir.module("C").ref("foo").field("bar")
+    val to = cir.module("D").instOf("e", "E").instOf("f", "F").ref("foo").field("foo")
+    renames.record(from, to)
+    renames.get(cir.module("A").instOf("b", "B").instOf("c", "C").ref("foo").field("bar")) should be {
+      Some(Seq(cir.module("A").instOf("b", "B").instOf("c", "D")
+        .instOf("e", "E").instOf("f", "F").ref("foo").field("foo")))
+    }
+  }
+
+  it should "error if an instance is renamed to a ReferenceTarget" in {
+    val top = CircuitTarget("Top").module("Top")
+    val renames = RenameMap()
+    val from = top.instOf("a", "A")
+    val to = top.ref("b")
+    renames.record(from, to)
+    a [IllegalRenameException] shouldBe thrownBy {
+      renames.get(from)
+    }
+  }
+
+  it should "not allow renaming of instances even if there is a matching reference rename" in {
+    val top = CircuitTarget("Top").module("Top")
+    val renames = RenameMap()
+    val from = top.ref("a")
+    val to = top.ref("b")
+    renames.record(from, to)
+    renames.get(top.instOf("a", "Foo")) should be (None)
+  }
+
+  it should "correctly chain renames together" in {
+    val top = CircuitTarget("Top")
+
+    val renames1 = RenameMap()
+    val from1 = top.module("A")
+    val to1 = top.module("Top").instOf("b", "B")
+    renames1.record(from1, to1)
+
+    val renames2 = RenameMap()
+    val from2 = top.module("B")
+    val to2 = top.module("B1")
+    renames2.record(from2, to2)
+
+    val renames = renames1.andThen(renames2)
+
+    renames.get(from1) should be {
+      Some(Seq(top.module("Top").instOf("b", "B1")))
+    }
+
+    renames.get(from2) should be {
+      Some(Seq(to2))
+    }
+  }
+
+  it should "correctly chain deleted targets" in {
+    val top = CircuitTarget("Top")
+    val modA = top.module("A")
+    val modA1 = top.module("A1")
+    val modB = top.module("B")
+    val modB1 = top.module("B1")
+
+    val renames1 = RenameMap()
+    renames1.delete(modA)
+    renames1.record(modB, modB1)
+
+    val renames2 = RenameMap()
+    renames2.record(modA, modA1)
+    renames2.delete(modB1)
+
+    val renames = renames1.andThen(renames2)
+
+    renames.get(modA) should be {
+      Some(Seq.empty)
+    }
+    renames.get(modB) should be {
+      Some(Seq.empty)
+    }
+  }
+
+  it should "correctly ++ renameMaps" in {
+    val top = CircuitTarget("Top")
+    val modA = top.module("A")
+    val modA1 = top.module("A1")
+    val modA2 = top.module("A1")
+    val modB = top.module("B")
+    val modB1 = top.module("B1")
+    val modC = top.module("C")
+    val modC1 = top.module("C1")
+
+    val renames1 = RenameMap()
+    renames1.record(modA, modA1)
+    renames1.record(modC, modC1)
+
+    val renames2 = RenameMap()
+    renames2.record(modA, modA2)
+    renames2.record(modB, modB1)
+
+    val renames = renames1 ++ renames2
+    renames.get(modA) should be {
+      Some(Seq(modA2))
+    }
+    renames.get(modB) should be {
+      Some(Seq(modB1))
+    }
+    renames.get(modC) should be {
+      Some(Seq(modC1))
+    }
+  }
+
+  it should "be able to inline instances" in {
+    val top = CircuitTarget("Top")
+    val inlineRename1 = {
+      val inlineMod = top.module("A")
+      val inlineInst = top.module("A").instOf("b", "B")
+      val oldRef = inlineMod.ref("bar")
+      val prefixRef = inlineMod.ref("foo")
+
+      val renames1 = RenameMap()
+      renames1.record(inlineInst, inlineMod)
+
+      val renames2 = RenameMap()
+      renames2.record(oldRef, prefixRef)
+
+      renames1.andThen(renames2)
+    }
+
+    val inlineRename2 = {
+      val inlineMod = top.module("A1")
+      val inlineInst = top.module("A1").instOf("b", "B1")
+      val oldRef = inlineMod.ref("bar")
+      val prefixRef = inlineMod.ref("foo")
+
+      val renames1 = RenameMap()
+      renames1.record(inlineInst, inlineMod)
+
+      val renames2 = RenameMap()
+      renames2.record(oldRef, prefixRef)
+
+      renames1.andThen(renames2)
+    }
+
+    val renames = inlineRename1 ++ inlineRename2
+    renames.get(top.module("A").instOf("b", "B").ref("bar")) should be {
+      Some(Seq(top.module("A").ref("foo")))
+    }
+
+    renames.get(top.module("A1").instOf("b", "B1").ref("bar")) should be {
+      Some(Seq(top.module("A1").ref("foo")))
+    }
+  }
+
+  it should "be able to dedup modules" in {
+    val top = CircuitTarget("Top")
+    val topMod = top.module("Top")
+    val dedupedMod = top.module("A")
+    val dupMod1 = top.module("A1")
+    val dupMod2 = top.module("A2")
+
+    val relPath1 = dupMod1.addHierarchy("Foo", "a")//top.module("Foo").instOf("a", "A1")
+    val relPath2 = dupMod2.addHierarchy("Foo", "a")//top.module("Foo").instOf("a", "A2")
+
+    val absPath1 = relPath1.addHierarchy("Top", "foo")
+    val absPath2 = relPath2.addHierarchy("Top", "foo")
+
+    val renames1 = RenameMap()
+    renames1.record(dupMod1, absPath1)
+    renames1.record(dupMod2, absPath2)
+    renames1.record(relPath1, absPath1)
+    renames1.record(relPath2, absPath2)
+
+    val renames2 = RenameMap()
+    renames2.record(dupMod1, dedupedMod)
+    renames2.record(dupMod2, dedupedMod)
+
+    val renames = renames1.andThen(renames2)
+
+    renames.get(dupMod1.instOf("foo", "Bar").ref("ref")) should be {
+      Some(Seq(absPath1.copy(ofModule = "A").instOf("foo", "Bar").ref("ref")))
+    }
+
+    renames.get(dupMod2.ref("ref")) should be {
+      Some(Seq(absPath2.copy(ofModule = "A").ref("ref")))
+    }
+
+    renames.get(absPath1.instOf("b", "B").ref("ref")) should be {
+      Some(Seq(absPath1.copy(ofModule = "A").instOf("b", "B").ref("ref")))
+    }
+  }
 }