safety_net/

netlist.rs

/*!

  API for a netlist data structure.

*/

use crate::{
    attribute::{Attribute, AttributeKey, AttributeValue, Parameter},
    circuit::{Identifier, Instantiable, Net, Object},
    error::Error,
    graph::{Analysis, FanOutTable},
    logic::Logic,
};
use std::{
    cell::{Ref, RefCell, RefMut},
    collections::{BTreeSet, HashMap, HashSet},
    num::ParseIntError,
    rc::{Rc, Weak},
};

/// A trait for indexing into a collection of objects weakly.
trait WeakIndex<Idx: ?Sized> {
    /// The output data type which will be referred to weakly
    type Output: ?Sized;
    /// Indexes the collection weakly by the given index.
    fn index_weak(&self, index: &Idx) -> Rc<RefCell<Self::Output>>;
}

/// A primitive gate in a digital circuit, such as AND, OR, NOT, etc.
/// VDD and GND are reserved to represent logic one and zero, respectively.
#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(::serde::Serialize, ::serde::Deserialize))]
pub struct Gate {
    /// The name of the primitive
    name: Identifier,
    /// Input ports, order matters
    inputs: Vec<Net>,
    /// Output ports, order matters
    outputs: Vec<Net>,
}

impl Instantiable for Gate {
    fn get_name(&self) -> &Identifier {
        &self.name
    }

    fn get_input_ports(&self) -> impl IntoIterator<Item = &Net> {
        &self.inputs
    }

    fn get_output_ports(&self) -> impl IntoIterator<Item = &Net> {
        &self.outputs
    }

    fn has_parameter(&self, _id: &Identifier) -> bool {
        false
    }

    fn get_parameter(&self, _id: &Identifier) -> Option<Parameter> {
        None
    }

    fn set_parameter(&mut self, _id: &Identifier, _val: Parameter) -> Option<Parameter> {
        None
    }

    fn parameters(&self) -> impl Iterator<Item = (Identifier, Parameter)> {
        std::iter::empty()
    }

    fn from_constant(val: Logic) -> Option<Self> {
        match val {
            Logic::True => Some(Gate::new_logical("VDD".into(), vec![], "Y".into())),
            Logic::False => Some(Gate::new_logical("GND".into(), vec![], "Y".into())),
            _ => None,
        }
    }

    fn get_constant(&self) -> Option<Logic> {
        match self.name.to_string().as_str() {
            "VDD" => Some(Logic::True),
            "GND" => Some(Logic::False),
            _ => None,
        }
    }

    fn is_seq(&self) -> bool {
        false
    }
}

impl Gate {
    /// Creates a new gate primitive with four-state logic types
    pub fn new_logical(name: Identifier, inputs: Vec<Identifier>, output: Identifier) -> Self {
        if name.is_sliced() {
            panic!("Attempted to create a gate with a sliced identifier: {name}");
        }

        let outputs = vec![Net::new_logic(output)];
        let inputs = inputs.into_iter().map(Net::new_logic).collect::<Vec<_>>();
        Self {
            name,
            inputs,
            outputs,
        }
    }

    /// Creates a new gate primitive with four-state logic types with multiple outputs
    pub fn new_logical_multi(
        name: Identifier,
        inputs: Vec<Identifier>,
        outputs: Vec<Identifier>,
    ) -> Self {
        if name.is_sliced() {
            panic!("Attempted to create a gate with a sliced identifier: {name}");
        }

        let outputs = outputs.into_iter().map(Net::new_logic).collect::<Vec<_>>();
        let inputs = inputs.into_iter().map(Net::new_logic).collect::<Vec<_>>();
        Self {
            name,
            inputs,
            outputs,
        }
    }

    /// Returns the single output port of the gate
    pub fn get_single_output_port(&self) -> &Net {
        if self.outputs.len() > 1 {
            panic!("Attempted to grab output port of a multi-output gate");
        }
        self.outputs
            .first()
            .expect("Gate is missing an output port")
    }

    /// Set the type of cell by name
    pub fn set_gate_name(&mut self, new_name: Identifier) {
        self.name = new_name;
    }

    /// Returns the name of the gate primitive
    pub fn get_gate_name(&self) -> &Identifier {
        &self.name
    }
}

/// An operand to an [Instantiable]
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(::serde::Serialize, ::serde::Deserialize))]
enum Operand {
    /// An index into the list of objects
    DirectIndex(usize),
    /// An index into the list of objects, with an extra index on the cell/primitive
    CellIndex(usize, usize),
}

impl Operand {
    /// Remap the node index of the operand to `x`.
    fn remap(self, x: usize) -> Self {
        match self {
            Operand::DirectIndex(_idx) => Operand::DirectIndex(x),
            Operand::CellIndex(_idx, j) => Operand::CellIndex(x, j),
        }
    }

    /// Returns the circuit node index
    fn root(&self) -> usize {
        match self {
            Operand::DirectIndex(idx) => *idx,
            Operand::CellIndex(idx, _) => *idx,
        }
    }

    /// Returns the secondary index (the cell index)
    fn secondary(&self) -> usize {
        match self {
            Operand::DirectIndex(_) => 0,
            Operand::CellIndex(_, j) => *j,
        }
    }
}

impl std::fmt::Display for Operand {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Operand::DirectIndex(idx) => write!(f, "{idx}"),
            Operand::CellIndex(idx, j) => write!(f, "{idx}.{j}"),
        }
    }
}

impl std::str::FromStr for Operand {
    type Err = ParseIntError;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        match s.split_once('.') {
            Some((idx, j)) => {
                let idx = idx.parse::<usize>()?;
                let j = j.parse::<usize>()?;
                Ok(Operand::CellIndex(idx, j))
            }
            None => {
                let idx = s.parse::<usize>()?;
                Ok(Operand::DirectIndex(idx))
            }
        }
    }
}

/// An object that has a reference to its owning netlist/module
#[derive(Debug)]
struct OwnedObject<I, O>
where
    I: Instantiable,
    O: WeakIndex<usize, Output = Self>,
{
    /// The object that is owned by the netlist
    object: Object<I>,
    /// The weak reference to the owner netlist/module
    owner: Weak<O>,
    /// The list of operands for the object
    operands: Vec<Option<Operand>>,
    /// A collection of attributes for the object
    attributes: HashMap<AttributeKey, AttributeValue>,
    /// The index of the object within the netlist/module
    index: usize,
}

impl<I, O> OwnedObject<I, O>
where
    I: Instantiable,
    O: WeakIndex<usize, Output = Self>,
{
    /// Get an iterator to mutate the operand indices
    fn inds_mut(&mut self) -> impl Iterator<Item = &mut Operand> {
        self.operands
            .iter_mut()
            .filter_map(|operand| operand.as_mut())
    }

    /// Get the driver to input `index`
    fn get_driver(&self, index: usize) -> Option<Rc<RefCell<Self>>> {
        self.operands[index].as_ref().map(|operand| {
            self.owner
                .upgrade()
                .expect("Object is unlinked from netlist")
                .index_weak(&operand.root())
        })
    }

    /// Iterator to driving objects
    fn drivers(&self) -> impl Iterator<Item = Option<Rc<RefCell<Self>>>> {
        self.operands.iter().map(|operand| {
            operand.as_ref().map(|operand| {
                self.owner
                    .upgrade()
                    .expect("Object is unlinked from netlist")
                    .index_weak(&operand.root())
            })
        })
    }

    /// Iterator to driving nets
    fn driver_nets(&self) -> impl Iterator<Item = Option<Net>> {
        self.operands.iter().map(|operand| {
            operand.as_ref().map(|operand| match operand {
                Operand::DirectIndex(idx) => self
                    .owner
                    .upgrade()
                    .expect("Object is unlinked from netlist")
                    .index_weak(idx)
                    .borrow()
                    .as_net()
                    .clone(),
                Operand::CellIndex(idx, j) => self
                    .owner
                    .upgrade()
                    .expect("Object is unlinked from netlist")
                    .index_weak(idx)
                    .borrow()
                    .get_net(*j)
                    .clone(),
            })
        })
    }

    /// Get the underlying object
    fn get(&self) -> &Object<I> {
        &self.object
    }

    /// Get the underlying object mutably
    fn get_mut(&mut self) -> &mut Object<I> {
        &mut self.object
    }

    /// Get the index of `self` relative to the owning module
    fn get_index(&self) -> usize {
        self.index
    }

    /// Get the net that is driven by this object
    fn as_net(&self) -> &Net {
        match &self.object {
            Object::Input(net) => net,
            Object::Instance(nets, _, _) => {
                if nets.len() > 1 {
                    panic!("Attempt to grab the net of a multi-output instance");
                } else {
                    nets.first().expect("Instance is missing a net to drive")
                }
            }
        }
    }

    /// Get the net that is driven by this object
    fn as_net_mut(&mut self) -> &mut Net {
        match &mut self.object {
            Object::Input(net) => net,
            Object::Instance(nets, _, _) => {
                if nets.len() > 1 {
                    panic!("Attempt to grab the net of a multi-output instance");
                } else {
                    nets.first_mut()
                        .expect("Instance is missing a net to drive")
                }
            }
        }
    }

    /// Get the net that is driven by this object at position `idx`
    fn get_net(&self, idx: usize) -> &Net {
        match &self.object {
            Object::Input(net) => {
                if idx != 0 {
                    panic!("Nonzero index on an input object");
                }
                net
            }
            Object::Instance(nets, _, _) => &nets[idx],
        }
    }

    /// Get a mutable reference to the net that is driven by this object at position `idx`
    fn get_net_mut(&mut self, idx: usize) -> &mut Net {
        match &mut self.object {
            Object::Input(net) => {
                if idx != 0 {
                    panic!("Nonzero index on an input object");
                }
                net
            }
            Object::Instance(nets, _, _) => &mut nets[idx],
        }
    }

    /// Check if this object drives a specific net
    fn find_net(&self, net: &Net) -> Option<usize> {
        match &self.object {
            Object::Input(input_net) => {
                if input_net == net {
                    Some(0)
                } else {
                    None
                }
            }
            Object::Instance(nets, _, _) => nets.iter().position(|n| n == net),
        }
    }

    /// Attempt to find a mutable reference to a net within this object
    fn find_net_mut(&mut self, net: &Net) -> Option<&mut Net> {
        match &mut self.object {
            Object::Input(input_net) => {
                if input_net == net {
                    Some(input_net)
                } else {
                    None
                }
            }
            Object::Instance(nets, _, _) => nets.iter_mut().find(|n| *n == net),
        }
    }

    /// Get driving net using the weak reference
    ///
    /// # Panics
    ///
    /// Panics if the reference to the netlist is lost.
    fn get_driver_net(&self, index: usize) -> Option<Net> {
        let operand = &self.operands[index];
        match operand {
            Some(op) => match op {
                Operand::DirectIndex(idx) => self
                    .owner
                    .upgrade()
                    .expect("Object is unlinked from netlist")
                    .index_weak(idx)
                    .borrow()
                    .as_net()
                    .clone()
                    .into(),
                Operand::CellIndex(idx, j) => self
                    .owner
                    .upgrade()
                    .expect("Object is unlinked from netlist")
                    .index_weak(idx)
                    .borrow()
                    .get_net(*j)
                    .clone()
                    .into(),
            },
            None => None,
        }
    }

    fn clear_attribute(&mut self, k: &AttributeKey) -> Option<AttributeValue> {
        self.attributes.remove(k)
    }

    fn set_attribute(&mut self, k: AttributeKey) {
        self.attributes.insert(k, None);
    }

    fn insert_attribute(&mut self, k: AttributeKey, v: String) -> Option<AttributeValue> {
        self.attributes.insert(k, Some(v))
    }

    fn attributes(&self) -> impl Iterator<Item = Attribute> {
        Attribute::from_pairs(self.attributes.clone().into_iter())
    }
}

/// This type exposes the interior mutability of elements in a netlist.
type NetRefT<I> = Rc<RefCell<OwnedObject<I, Netlist<I>>>>;

/// Provides an idiomatic interface
/// to the interior mutability of the netlist
#[derive(Clone)]
pub struct NetRef<I>
where
    I: Instantiable,
{
    netref: NetRefT<I>,
}

impl<I> std::fmt::Debug for NetRef<I>
where
    I: Instantiable,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let b = self.netref.borrow();
        let o = b.get();
        let i = b.index;
        let owner = &b.owner;
        match owner.upgrade() {
            Some(owner) => {
                let n = owner.get_name();
                write!(f, "{{ owner: \"{n}\", index: {i}, val: \"{o}\" }}")
            }
            None => write!(f, "{{ owner: None, index: {i}, val: \"{o}\" }}"),
        }
    }
}

impl<I> PartialEq for NetRef<I>
where
    I: Instantiable,
{
    fn eq(&self, other: &Self) -> bool {
        Rc::ptr_eq(&self.netref, &other.netref)
    }
}

impl<I> Eq for NetRef<I> where I: Instantiable {}

impl<I> Ord for NetRef<I>
where
    I: Instantiable,
{
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        Rc::as_ptr(&self.netref).cmp(&Rc::as_ptr(&other.netref))
    }
}

impl<I> PartialOrd for NetRef<I>
where
    I: Instantiable,
{
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl<I> std::hash::Hash for NetRef<I>
where
    I: Instantiable,
{
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        Rc::as_ptr(&self.netref).hash(state);
    }
}

impl<I> NetRef<I>
where
    I: Instantiable,
{
    /// Creates a new [NetRef] from a [NetRefT]
    fn wrap(netref: NetRefT<I>) -> Self {
        Self { netref }
    }

    /// Returns the underlying [NetRefT]
    fn unwrap(self) -> NetRefT<I> {
        self.netref
    }

    /// Returns a borrow to the [Net] at this circuit node.
    ///
    /// # Panics
    ///
    /// Panics if the circuit node has multiple outputs.
    pub fn as_net(&self) -> Ref<'_, Net> {
        Ref::map(self.netref.borrow(), |f| f.as_net())
    }

    /// Returns a mutable borrow to the [Net] at this circuit node.
    ///
    /// # Panics
    ///
    /// Panics if the circuit node has multiple outputs.
    pub fn as_net_mut(&self) -> RefMut<'_, Net> {
        RefMut::map(self.netref.borrow_mut(), |f| f.as_net_mut())
    }

    /// Returns a borrow to the output [Net] as position `idx`
    pub fn get_net(&self, idx: usize) -> Ref<'_, Net> {
        Ref::map(self.netref.borrow(), |f| f.get_net(idx))
    }

    /// Returns a mutable borrow to the output [Net] as position `idx`
    pub fn get_net_mut(&self, idx: usize) -> RefMut<'_, Net> {
        RefMut::map(self.netref.borrow_mut(), |f| f.get_net_mut(idx))
    }

    /// Returns a borrow to the output [Net] as position `idx`
    pub fn get_output(&self, idx: usize) -> DrivenNet<I> {
        DrivenNet::new(idx, self.clone())
    }

    /// Returns a borrow to the output connected to port `id`
    pub fn find_output(&self, id: &Identifier) -> Option<DrivenNet<I>> {
        let ind = self.get_instance_type()?.find_output(id)?;
        Some(self.get_output(ind))
    }

    /// Returns an abstraction around the input connection
    pub fn get_input(&self, idx: usize) -> InputPort<I> {
        if self.is_an_input() {
            panic!("Principal inputs do not have inputs");
        }
        InputPort::new(idx, self.clone())
    }

    /// Returns a borrow to the input port with name `id`
    pub fn find_input(&self, id: &Identifier) -> Option<InputPort<I>> {
        let ind = self.get_instance_type()?.find_input(id)?;
        Some(self.get_input(ind))
    }

    /// Returns the name of the net at this circuit node.
    ///
    /// # Panics
    ///
    /// Panics if the circuit node has multiple outputs.
    pub fn get_identifier(&self) -> Identifier {
        self.as_net().get_identifier().clone()
    }

    /// Changes the identifier of the net at this circuit node.
    ///
    /// # Panics
    ///
    /// Panics if the circuit node has multiple outputs.
    pub fn set_identifier(&self, identifier: Identifier) {
        self.as_net_mut().set_identifier(identifier)
    }

    /// Returns `true` if this circuit node is a principal input
    pub fn is_an_input(&self) -> bool {
        matches!(self.netref.borrow().get(), Object::Input(_))
    }

    /// Returns a reference to the object at this node.
    pub fn get_obj(&self) -> Ref<'_, Object<I>> {
        Ref::map(self.netref.borrow(), |f| f.get())
    }

    /// Returns the [Instantiable] type of the instance, if this circuit node is an instance
    pub fn get_instance_type(&self) -> Option<Ref<'_, I>> {
        Ref::filter_map(self.netref.borrow(), |f| f.get().get_instance_type()).ok()
    }

    /// Returns the [Instantiable] type of the instance, if this circuit node is an instance
    pub fn get_instance_type_mut(&self) -> Option<RefMut<'_, I>> {
        RefMut::filter_map(self.netref.borrow_mut(), |f| {
            f.get_mut().get_instance_type_mut()
        })
        .ok()
    }

    /// Returns a copy of the name of the instance, if the circuit node is a instance.
    pub fn get_instance_name(&self) -> Option<Identifier> {
        match self.netref.borrow().get() {
            Object::Instance(_, inst_name, _) => Some(inst_name.clone()),
            _ => None,
        }
    }

    /// Updates the name of the instance, if the circuit node is an instance.
    ///
    /// # Panics
    ///
    /// Panics if the circuit node is a principal input.
    pub fn set_instance_name(&self, name: Identifier) {
        match self.netref.borrow_mut().get_mut() {
            Object::Instance(_, inst_name, _) => *inst_name = name,
            _ => panic!("Attempted to set instance name on a non-instance object"),
        }
    }

    /// Exposes this circuit node as a top-level output in the netlist.
    /// Returns an error if the circuit node is a principal input.
    ///
    /// # Panics
    ///
    /// Panics if cell is a multi-output circuit node.
    /// Panics if the reference to the netlist is lost.
    pub fn expose_as_output(self) -> Result<Self, Error> {
        let netlist = self
            .netref
            .borrow()
            .owner
            .upgrade()
            .expect("NetRef is unlinked from netlist");
        netlist.expose_net(self.clone().into())?;
        Ok(self)
    }

    /// Exposes this circuit node as a top-level output in the netlist with a specific port name.
    /// Multiple calls to this method can be used to create multiple output aliases for the same net.
    ///
    /// # Panics
    ///
    /// Panics if the cell is a multi-output circuit node.
    /// Panics if the reference to the netlist is lost.
    pub fn expose_with_name(self, name: Identifier) -> Self {
        let netlist = self
            .netref
            .borrow()
            .owner
            .upgrade()
            .expect("NetRef is unlinked from netlist");
        netlist.expose_net_with_name(self.clone().into(), name);
        self
    }

    /// Exposes the `net` driven by this circuit node as a top-level output.
    /// Errors if `net` is not driven by this circuit node.
    ///
    /// # Panics
    /// Panics if the reference to the netlist is lost.
    pub fn expose_net(&self, net: &Net) -> Result<(), Error> {
        let netlist = self
            .netref
            .borrow()
            .owner
            .upgrade()
            .expect("NetRef is unlinked from netlist");
        let net_index = self
            .netref
            .borrow()
            .find_net(net)
            .ok_or(Error::NetNotFound(net.clone()))?;
        let dr = DrivenNet::new(net_index, self.clone());
        netlist.expose_net(dr)?;
        Ok(())
    }

    /// Removes a specific output alias by its name from this circuit node.
    /// Returns true if the output was removed, false if it didn't exist.
    ///
    /// # Panics
    ///
    /// Panics if cell is a multi-output circuit node.
    /// Panics if the reference to the netlist is lost.
    pub fn remove_output(&self, net_name: &Identifier) -> bool {
        let netlist = self
            .netref
            .borrow()
            .owner
            .upgrade()
            .expect("NetRef is unlinked from netlist");
        netlist.remove_output(&self.into(), net_name)
    }

    /// Removes all output aliases for this circuit node.
    /// Returns the number of outputs that were removed.
    ///
    /// # Panics
    ///
    /// Panics if cell is a multi-output circuit node.
    /// Panics if the reference to the netlist is lost.
    pub fn remove_all_outputs(&self) -> usize {
        let netlist = self
            .netref
            .borrow()
            .owner
            .upgrade()
            .expect("NetRef is unlinked from netlist");
        netlist.remove_outputs(&self.into())
    }

    /// Returns the circuit node that drives the `index`th input
    pub fn get_driver(&self, index: usize) -> Option<Self> {
        self.netref.borrow().get_driver(index).map(NetRef::wrap)
    }

    /// Returns the net that drives the `index`th input
    ///
    /// # Panics
    ///
    /// Panics if the reference to the netlist is lost.
    pub fn get_driver_net(&self, index: usize) -> Option<Net> {
        self.netref.borrow().get_driver_net(index)
    }

    /// Returns a request to mutably borrow the operand net
    /// This requires another borrow in the form of [MutBorrowReq]
    ///
    /// # Panics
    ///
    /// Panics if the reference to the netlist is lost.
    pub fn req_driver_net(&self, index: usize) -> Option<MutBorrowReq<I>> {
        let net = self.get_driver_net(index)?;
        let operand = self.get_driver(index).unwrap();
        Some(MutBorrowReq::new(operand, net))
    }

    /// Returns the number of input ports for this circuit node.
    pub fn get_num_input_ports(&self) -> usize {
        if let Some(inst_type) = self.get_instance_type() {
            inst_type.get_input_ports().into_iter().count()
        } else {
            0
        }
    }

    /// Returns `true` if this circuit node has all its input ports connected.
    pub fn is_fully_connected(&self) -> bool {
        assert_eq!(
            self.netref.borrow().operands.len(),
            self.get_num_input_ports()
        );
        self.netref.borrow().operands.iter().all(|o| o.is_some())
    }

    /// Returns an iterator to the driving circuit nodes.
    pub fn drivers(&self) -> impl Iterator<Item = Option<Self>> {
        let drivers: Vec<Option<Self>> = self
            .netref
            .borrow()
            .drivers()
            .map(|o| o.map(NetRef::wrap))
            .collect();
        drivers.into_iter()
    }

    /// Returns an interator to the driving nets.
    pub fn driver_nets(&self) -> impl Iterator<Item = Option<Net>> {
        let vec: Vec<Option<Net>> = self.netref.borrow().driver_nets().collect();
        vec.into_iter()
    }

    /// Returns an iterator to the output nets of this circuit node.
    #[allow(clippy::unnecessary_to_owned)]
    pub fn nets(&self) -> impl Iterator<Item = Net> {
        self.netref.borrow().get().get_nets().to_vec().into_iter()
    }

    /// Returns an iterator to the output nets of this circuit node, along with port information.
    pub fn inputs(&self) -> impl Iterator<Item = InputPort<I>> {
        let len = self.netref.borrow().operands.len();
        (0..len).map(move |i| InputPort::new(i, self.clone()))
    }

    /// Returns an iterator to the output nets of this circuit node, along with port information.
    pub fn outputs(&self) -> impl Iterator<Item = DrivenNet<I>> {
        let len = self.netref.borrow().get().get_nets().len();
        (0..len).map(move |i| DrivenNet::new(i, self.clone()))
    }

    /// Returns an iterator to mutate the output nets of this circuit node.
    pub fn nets_mut(&self) -> impl Iterator<Item = RefMut<'_, Net>> {
        let nnets = self.netref.borrow().get().get_nets().len();
        (0..nnets).map(|i| self.get_net_mut(i))
    }

    /// Returns `true` if this circuit node drives the given net.
    pub fn drives_net(&self, net: &Net) -> bool {
        self.netref.borrow().find_net(net).is_some()
    }

    /// Returns `true` if this circuit node drives a top-level output.
    ///
    /// # Panics
    /// Panics if the weak reference to the netlist is lost.
    pub fn drives_a_top_output(&self) -> bool {
        let netlist = self
            .netref
            .borrow()
            .owner
            .upgrade()
            .expect("NetRef is unlinked from netlist");
        netlist.drives_an_output(self.clone())
    }

    /// Attempts to find a mutable reference to `net` within this circuit node.
    pub fn find_net_mut(&self, net: &Net) -> Option<RefMut<'_, Net>> {
        RefMut::filter_map(self.netref.borrow_mut(), |f| f.find_net_mut(net)).ok()
    }

    /// Returns `true` if this circuit node has multiple outputs/nets.
    pub fn is_multi_output(&self) -> bool {
        self.netref.borrow().get().get_nets().len() > 1
    }

    /// Deletes the uses of this circuit node from the netlist.
    ///
    /// # Panics
    ///
    /// Panics if the reference to the netlist is lost.
    pub fn delete_uses(self) -> Result<Object<I>, Error> {
        let netlist = self
            .netref
            .borrow()
            .owner
            .upgrade()
            .expect("NetRef is unlinked from netlist");
        netlist.delete_net_uses(self)
    }

    /// Replaces the uses of this circuit node in the netlist with another circuit node.
    ///
    /// # See also:
    /// - [`NetMapper`](rewriter::NetMapper)
    ///
    /// # Panics
    ///
    /// Panics if either `self` is a multi-output circuit node.
    /// Panics if the weak reference to the netlist is lost.
    pub fn replace_uses_with(self, other: &DrivenNet<I>) -> Result<NetRef<I>, Error> {
        let netlist = self
            .netref
            .borrow()
            .owner
            .upgrade()
            .expect("NetRef is unlinked from netlist");
        netlist
            .replace_net_uses(self.into(), other)
            .map(|d| d.unwrap())
    }

    /// Clears the attribute with the given key on this circuit node.
    pub fn clear_attribute(&self, k: &AttributeKey) -> Option<AttributeValue> {
        self.netref.borrow_mut().clear_attribute(k)
    }

    /// Set an attribute without a value
    pub fn set_attribute(&self, k: AttributeKey) {
        self.netref.borrow_mut().set_attribute(k);
    }

    /// Insert an attribute on this node with a value
    pub fn insert_attribute(&self, k: AttributeKey, v: String) -> Option<AttributeValue> {
        self.netref.borrow_mut().insert_attribute(k, v)
    }

    /// Returns an iterator to the attributes at this circuit node
    pub fn attributes(&self) -> impl Iterator<Item = Attribute> {
        let v: Vec<_> = self.netref.borrow().attributes().collect();
        v.into_iter()
    }
}

impl<I> std::fmt::Display for NetRef<I>
where
    I: Instantiable,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.netref.borrow().object.fmt(f)
    }
}

impl<I> From<NetRef<I>> for DrivenNet<I>
where
    I: Instantiable,
{
    fn from(val: NetRef<I>) -> Self {
        if val.is_multi_output() {
            panic!("Cannot convert a multi-output netref to an output port");
        }
        DrivenNet::new(0, val)
    }
}

impl<I> From<&NetRef<I>> for DrivenNet<I>
where
    I: Instantiable,
{
    fn from(val: &NetRef<I>) -> Self {
        if val.is_multi_output() {
            panic!("Cannot convert a multi-output netref to an output port");
        }
        DrivenNet::new(0, val.clone())
    }
}

/// Facilitates mutable borrows to driver nets
pub struct MutBorrowReq<I: Instantiable> {
    from: NetRef<I>,
    ind: Net,
}

impl<I> MutBorrowReq<I>
where
    I: Instantiable,
{
    /// Creates a new mutable borrow request
    fn new(from: NetRef<I>, ind: Net) -> Self {
        Self { from, ind }
    }

    /// Mutably borrows the requested net from the circuit node
    pub fn borrow_mut(&self) -> RefMut<'_, Net> {
        self.from.find_net_mut(&self.ind).unwrap()
    }

    /// Returns `true` if the circuit node is an input
    pub fn is_an_input(&self) -> bool {
        self.from.is_an_input()
    }

    /// Attempts to borrow the net mutably if the condition `f` is satisfied.
    pub fn borrow_mut_if(&self, f: impl Fn(&NetRef<I>) -> bool) -> Option<RefMut<'_, Net>> {
        if f(&self.from) {
            Some(self.borrow_mut())
        } else {
            None
        }
    }
}

/// A netlist data structure
#[derive(Debug)]
pub struct Netlist<I>
where
    I: Instantiable,
{
    /// The name of the netlist
    name: RefCell<String>,
    /// The list of objects in the netlist, such as inputs, modules, and primitives
    objects: RefCell<Vec<NetRefT<I>>>,
    /// Each operand can map to multiple nets, supporting output aliases.
    outputs: RefCell<HashMap<Operand, BTreeSet<Net>>>,
}

/// Represent the input port of a primitive
#[derive(Debug, Clone)]
pub struct InputPort<I: Instantiable> {
    pos: usize,
    netref: NetRef<I>,
}

impl<I> InputPort<I>
where
    I: Instantiable,
{
    fn new(pos: usize, netref: NetRef<I>) -> Self {
        if pos >= netref.clone().unwrap().borrow().operands.len() {
            panic!(
                "Position {} out of bounds for netref with {} input nets",
                pos,
                netref.unwrap().borrow().get().get_nets().len()
            );
        }
        Self { pos, netref }
    }

    /// Returns the net that is driving this input port
    pub fn get_driver(&self) -> Option<DrivenNet<I>> {
        if self.netref.is_an_input() {
            panic!("Input port is not driven by a primitive");
        }
        if let Some(prev_operand) = self.netref.clone().unwrap().borrow().operands[self.pos] {
            let netlist = self
                .netref
                .clone()
                .unwrap()
                .borrow()
                .owner
                .upgrade()
                .expect("Input port is unlinked from netlist");
            let driver_nr = netlist.index_weak(&prev_operand.root());
            let nr = NetRef::wrap(driver_nr);
            let pos = prev_operand.secondary();
            Some(DrivenNet::new(pos, nr))
        } else {
            None
        }
    }

    /// Disconnects an input port and returns the previous [DrivenNet] if it was connected.
    pub fn disconnect(&self) -> Option<DrivenNet<I>> {
        let val = self.get_driver();
        self.netref.clone().unwrap().borrow_mut().operands[self.pos] = None;
        val
    }

    /// Get the input port associated with this connection
    pub fn get_port(&self) -> Net {
        if self.netref.is_an_input() {
            panic!("Net is not driven by a primitive");
        }
        self.netref
            .get_instance_type()
            .unwrap()
            .get_input_port(self.pos)
            .clone()
    }

    /// Connects this input port to a driven net.
    pub fn connect(self, output: DrivenNet<I>) {
        output.connect(self);
    }

    /// Return the underlying circuit node
    pub fn unwrap(self) -> NetRef<I> {
        self.netref
    }

    /// Returns the index associated with this input port
    pub fn get_input_num(&self) -> usize {
        self.pos
    }
}

impl<I> std::fmt::Display for InputPort<I>
where
    I: Instantiable,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.get_port().fmt(f)
    }
}

/// Represent a net that is being driven by a [Instantiable]
#[derive(Debug, Clone)]
pub struct DrivenNet<I: Instantiable> {
    pos: usize,
    netref: NetRef<I>,
}

impl<I> DrivenNet<I>
where
    I: Instantiable,
{
    fn new(pos: usize, netref: NetRef<I>) -> Self {
        if pos >= netref.clone().unwrap().borrow().get().get_nets().len() {
            panic!(
                "Position {} out of bounds for netref with {} outputted nets",
                pos,
                netref.unwrap().borrow().get().get_nets().len()
            );
        }
        Self { pos, netref }
    }

    /// Returns the index that can address this net in the netlist.
    fn get_operand(&self) -> Operand {
        if self.netref.is_multi_output() {
            Operand::CellIndex(self.netref.clone().unwrap().borrow().get_index(), self.pos)
        } else {
            Operand::DirectIndex(self.netref.clone().unwrap().borrow().get_index())
        }
    }

    /// Borrow the net being driven
    pub fn as_net(&self) -> Ref<'_, Net> {
        self.netref.get_net(self.pos)
    }

    /// Get a mutable reference to the net being driven
    pub fn as_net_mut(&self) -> RefMut<'_, Net> {
        self.netref.get_net_mut(self.pos)
    }

    /// Returns `true` if this net is a principal input
    pub fn is_an_input(&self) -> bool {
        self.netref.is_an_input()
    }

    /// Get the output port associated with this connection
    pub fn get_port(&self) -> Net {
        if self.netref.is_an_input() {
            panic!("Net is not driven by a primitive");
        }
        self.netref
            .get_instance_type()
            .unwrap()
            .get_output_port(self.pos)
            .clone()
    }

    /// Connects the net driven by this output port to the given input port.
    pub fn connect(&self, input: InputPort<I>) {
        let operand = self.get_operand();
        let index = input.netref.unwrap().borrow().get_index();
        let netlist = self
            .netref
            .clone()
            .unwrap()
            .borrow()
            .owner
            .upgrade()
            .expect("Output port is unlinked from netlist");
        let obj = netlist.index_weak(&index);
        obj.borrow_mut().operands[input.pos] = Some(operand);
    }

    /// Returns `true` if this net is a top-level output in the netlist.
    pub fn is_top_level_output(&self) -> bool {
        let netlist = self
            .netref
            .clone()
            .unwrap()
            .borrow()
            .owner
            .upgrade()
            .expect("DrivenNet is unlinked from netlist");
        let outputs = netlist.outputs.borrow();
        outputs.contains_key(&self.get_operand())
    }

    /// Return the underlying circuit node
    pub fn unwrap(self) -> NetRef<I> {
        self.netref
    }

    /// Returns a copy of the identifier of the net being driven.
    pub fn get_identifier(&self) -> Identifier {
        self.as_net().get_identifier().clone()
    }

    /// Exposes this driven net as a top-level output with a specific port name.
    /// Multiple calls to this method can be used to create multiple output aliases for the same net.
    ///
    /// # Panics
    ///
    /// Panics if the weak reference to the netlist is dead.
    pub fn expose_with_name(self, name: Identifier) -> Self {
        let netlist = self
            .netref
            .clone()
            .unwrap()
            .borrow()
            .owner
            .upgrade()
            .expect("DrivenNet is unlinked from netlist");
        netlist.expose_net_with_name(self.clone(), name);
        self
    }

    /// Removes a specific output alias by its name from this driven net.
    /// Returns true if the output was removed, false if it didn't exist.
    ///
    /// # Panics
    ///
    /// Panics if the reference to the netlist is lost.
    pub fn remove_output(&self, net_name: &Identifier) -> bool {
        let netlist = self
            .netref
            .clone()
            .unwrap()
            .borrow()
            .owner
            .upgrade()
            .expect("DrivenNet is unlinked from netlist");
        netlist.remove_output(self, net_name)
    }

    /// Removes all output aliases for this driven net.
    /// Returns the number of outputs that were removed.
    ///
    /// # Panics
    ///
    /// Panics if the reference to the netlist is lost.
    pub fn remove_all_outputs(&self) -> usize {
        let netlist = self
            .netref
            .clone()
            .unwrap()
            .borrow()
            .owner
            .upgrade()
            .expect("DrivenNet is unlinked from netlist");
        netlist.remove_outputs(self)
    }

    /// Returns the output position, if the net is the output of a gate.
    pub fn get_output_index(&self) -> Option<usize> {
        if self.netref.is_an_input() {
            None
        } else {
            Some(self.pos)
        }
    }

    /// Returns the [Instantiable] type driving this net, if it has a driver.
    pub fn get_instance_type(&self) -> Option<Ref<'_, I>> {
        self.netref.get_instance_type()
    }
}

impl<I> std::fmt::Display for DrivenNet<I>
where
    I: Instantiable,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.as_net().fmt(f)
    }
}

impl<I> PartialEq for DrivenNet<I>
where
    I: Instantiable,
{
    fn eq(&self, other: &Self) -> bool {
        self.netref == other.netref && self.pos == other.pos
    }
}

impl<I> Eq for DrivenNet<I> where I: Instantiable {}

impl<I> std::hash::Hash for DrivenNet<I>
where
    I: Instantiable,
{
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.netref.hash(state);
        self.pos.hash(state);
    }
}

impl<I> Ord for DrivenNet<I>
where
    I: Instantiable,
{
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        match self.netref.cmp(&other.netref) {
            std::cmp::Ordering::Equal => self.pos.cmp(&other.pos),
            ord => ord,
        }
    }
}

impl<I> PartialOrd for DrivenNet<I>
where
    I: Instantiable,
{
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl<I> WeakIndex<usize> for Netlist<I>
where
    I: Instantiable,
{
    type Output = OwnedObject<I, Self>;

    fn index_weak(&self, index: &usize) -> Rc<RefCell<Self::Output>> {
        self.objects.borrow()[*index].clone()
    }
}

impl<I> Netlist<I>
where
    I: Instantiable,
{
    /// Creates a new netlist with the given name
    pub fn new(name: String) -> Rc<Self> {
        Rc::new(Self {
            name: RefCell::new(name),
            objects: RefCell::new(Vec::new()),
            outputs: RefCell::new(HashMap::new()),
        })
    }

    /// Attempts to reclaim the netlist, returning [Some] if successful.
    pub fn reclaim(self: Rc<Self>) -> Option<Self> {
        Rc::try_unwrap(self).ok()
    }

    /// Creates a deep clone of the netlist.
    pub fn deep_clone(self: &Rc<Self>) -> Rc<Self> {
        let dc = Rc::new(Self {
            name: self.name.clone(),
            objects: RefCell::new(Vec::new()),
            outputs: self.outputs.clone(),
        });

        let objects_linked: Vec<NetRefT<I>> = self
            .objects
            .borrow()
            .iter()
            .map(|obj| {
                Rc::new(RefCell::new(OwnedObject {
                    object: obj.borrow().object.clone(),
                    owner: Rc::downgrade(&dc),
                    operands: obj.borrow().operands.clone(),
                    attributes: obj.borrow().attributes.clone(),
                    index: obj.borrow().index,
                }))
            })
            .collect();

        *dc.objects.borrow_mut() = objects_linked;

        dc
    }

    /// Use interior mutability to add an object to the netlist. Returns a mutable reference to the created object.
    ///
    /// # Panics
    /// If any of the `operands` do not belong to this netlist.
    fn insert_object(
        self: &Rc<Self>,
        object: Object<I>,
        operands: &[DrivenNet<I>],
    ) -> Result<NetRef<I>, Error> {
        for operand in operands {
            self.belongs(&operand.clone().unwrap());
        }
        let index = self.objects.borrow().len();
        let weak = Rc::downgrade(self);
        let operands = operands
            .iter()
            .map(|net| Some(net.get_operand()))
            .collect::<Vec<_>>();
        let owned_object = Rc::new(RefCell::new(OwnedObject {
            object,
            owner: weak,
            operands,
            attributes: HashMap::new(),
            index,
        }));
        self.objects.borrow_mut().push(owned_object.clone());
        Ok(NetRef::wrap(owned_object))
    }

    /// Inserts an input net to the netlist
    pub fn insert_input(self: &Rc<Self>, net: Net) -> DrivenNet<I> {
        let obj = Object::Input(net);
        self.insert_object(obj, &[]).unwrap().into()
    }

    /// Inserts a four-state logic input port to the netlist
    pub fn insert_input_escaped_logic_bus(
        self: &Rc<Self>,
        net: String,
        bw: usize,
    ) -> Vec<DrivenNet<I>> {
        Net::new_escaped_logic_bus(net, bw)
            .into_iter()
            .map(|n| self.insert_input(n))
            .collect()
    }

    /// Inserts a gate to the netlist
    pub fn insert_gate(
        self: &Rc<Self>,
        inst_type: I,
        inst_name: Identifier,
        operands: &[DrivenNet<I>],
    ) -> Result<NetRef<I>, Error> {
        let nets = inst_type
            .get_output_ports()
            .into_iter()
            .map(|pnet| pnet.with_name(&inst_name + pnet.get_identifier()))
            .collect::<Vec<_>>();
        let input_count = inst_type.get_input_ports().into_iter().count();
        if operands.len() != input_count {
            return Err(Error::ArgumentMismatch(input_count, operands.len()));
        }
        let obj = Object::Instance(nets, inst_name, inst_type);
        self.insert_object(obj, operands)
    }

    /// Use interior mutability to add an object to the netlist. Returns a mutable reference to the created object.
    pub fn insert_gate_disconnected(
        self: &Rc<Self>,
        inst_type: I,
        inst_name: Identifier,
    ) -> NetRef<I> {
        let nets = inst_type
            .get_output_ports()
            .into_iter()
            .map(|pnet| pnet.with_name(&inst_name + pnet.get_identifier()))
            .collect::<Vec<_>>();
        let object = Object::Instance(nets, inst_name, inst_type);
        let index = self.objects.borrow().len();
        let weak = Rc::downgrade(self);
        let input_count = object
            .get_instance_type()
            .unwrap()
            .get_input_ports()
            .into_iter()
            .count();
        let operands = vec![None; input_count];
        let owned_object = Rc::new(RefCell::new(OwnedObject {
            object,
            owner: weak,
            operands,
            attributes: HashMap::new(),
            index,
        }));
        self.objects.borrow_mut().push(owned_object.clone());
        NetRef::wrap(owned_object)
    }

    /// Inserts a constant [Logic] value to the netlist
    pub fn insert_constant(
        self: &Rc<Self>,
        value: Logic,
        inst_name: Identifier,
    ) -> Result<DrivenNet<I>, Error> {
        let obj = I::from_constant(value).ok_or(Error::InstantiableError(format!(
            "Instantiable type does not support constant value {}",
            value
        )))?;
        Ok(self.insert_gate_disconnected(obj, inst_name).into())
    }

    /// # Panics
    ///
    /// Panics if `netref` definitely does not belong to this netlist.
    fn belongs(&self, netref: &NetRef<I>) {
        if let Some(nl) = netref.netref.borrow().owner.upgrade() {
            if self.objects.borrow().len() != nl.objects.borrow().len() {
                panic!("NetRef does not belong to this netlist");
            }

            if let Some(p) = self.objects.borrow().first()
                && let Some(np) = nl.objects.borrow().first()
                && !Rc::ptr_eq(p, np)
            {
                panic!("NetRef does not belong to this netlist");
            }
        }

        if netref.netref.borrow().index >= self.objects.borrow().len() {
            panic!("NetRef does not belong to this netlist");
        }
    }

    /// Returns the driving node at input position `index` for `netref`
    ///
    /// # Panics
    ///
    /// Panics if `index` is out of bounds
    /// The `netref` does not belong to this netlist
    pub fn get_driver(&self, netref: NetRef<I>, index: usize) -> Option<DrivenNet<I>> {
        self.belongs(&netref);
        let op = netref.unwrap().borrow().operands[index]?;
        Some(DrivenNet::new(
            op.secondary(),
            NetRef::wrap(self.index_weak(&op.root()).clone()),
        ))
    }

    /// Set an added object as a top-level output with a specific name.
    /// Multiple calls with different names for the same net will create multiple aliases.
    ///
    /// # Panics
    /// The `net` does not belong to this netlist
    pub fn expose_net_with_name(&self, net: DrivenNet<I>, name: Identifier) -> DrivenNet<I> {
        self.belongs(&net.clone().unwrap());
        let mut outputs = self.outputs.borrow_mut();
        let named_net = net.as_net().with_name(name);
        outputs
            .entry(net.get_operand())
            .or_default()
            .insert(named_net);
        net
    }

    /// Sets the current net as a top-level output using the current name of the net
    ///
    /// # Panics
    /// The `net` does not belong to this netlist
    pub fn expose_net(&self, net: DrivenNet<I>) -> Result<DrivenNet<I>, Error> {
        self.belongs(&net.clone().unwrap());
        if net.is_an_input() {
            return Err(Error::InputNeedsAlias(net.as_net().clone()));
        }
        let mut outputs = self.outputs.borrow_mut();
        outputs
            .entry(net.get_operand())
            .or_default()
            .insert(net.as_net().clone());
        Ok(net)
    }

    /// Removes a specific output alias by its operand and net name.
    /// Returns true if the output was removed, false if it didn't exist.
    ///
    /// # Panics
    /// The `operand` does not belong to this netlist
    pub fn remove_output(&self, operand: &DrivenNet<I>, net_name: &Identifier) -> bool {
        self.belongs(&operand.clone().unwrap());
        let mut outputs = self.outputs.borrow_mut();
        if let Some(nets) = outputs.get_mut(&operand.get_operand()) {
            // Create a net with just the identifier to match for removal
            let net_to_remove = Net::new(net_name.clone(), crate::circuit::DataType::logic());
            if nets.remove(&net_to_remove) {
                // If the set is now empty, remove the operand entirely
                if nets.is_empty() {
                    outputs.remove(&operand.get_operand());
                }
                return true;
            }
        }
        false
    }

    /// Removes all output aliases for a specific operand.
    /// Returns the number of outputs that were removed.
    pub fn remove_outputs(&self, operand: &DrivenNet<I>) -> usize {
        //let mut outputs = self.outputs.borrow_mut();
        self.outputs
            .borrow_mut()
            .remove(&operand.get_operand())
            .map(|nets| nets.len())
            .unwrap_or(0)
    }

    /// Removes all outputs from the netlist.
    pub fn clear_outputs(&self) {
        self.outputs.borrow_mut().clear();
    }

    /// Unlink a circuit node from the rest of the netlist. Return the object that was being stored.
    ///
    /// # Panics
    /// The `netref` does not belong to this netlist
    pub fn delete_net_uses(&self, netref: NetRef<I>) -> Result<Object<I>, Error> {
        self.belongs(&netref);
        let unwrapped = netref.clone().unwrap();
        if Rc::strong_count(&unwrapped) > 3 {
            return Err(Error::DanglingReference(netref.nets().collect()));
        }
        let old_index = unwrapped.borrow().get_index();
        let objects = self.objects.borrow();
        for oref in objects.iter() {
            let operands = &mut oref.borrow_mut().operands;
            for operand in operands.iter_mut() {
                if let Some(op) = operand {
                    match op {
                        Operand::DirectIndex(idx) | Operand::CellIndex(idx, _)
                            if *idx == old_index =>
                        {
                            *operand = None;
                        }
                        _ => (),
                    }
                }
            }
        }

        let outputs: Vec<Operand> = self
            .outputs
            .borrow()
            .keys()
            .filter(|operand| match operand {
                Operand::DirectIndex(idx) | Operand::CellIndex(idx, _) => *idx == old_index,
            })
            .cloned()
            .collect();

        for operand in outputs {
            self.outputs.borrow_mut().remove(&operand);
        }

        Ok(netref.unwrap().borrow().get().clone())
    }

    /// Replaces the uses of a circuit node with another circuit node. `of` is returned and unused.
    ///
    /// # See also:
    /// - [`NetMapper`](rewriter::NetMapper)
    ///
    /// # Panics
    /// `of` or `with` do not belong to this netlist
    pub fn replace_net_uses(
        &self,
        of: DrivenNet<I>,
        with: &DrivenNet<I>,
    ) -> Result<DrivenNet<I>, Error> {
        {
            self.belongs(&of.clone().unwrap());
            self.belongs(&with.clone().unwrap());
        }
        let unwrapped = of.clone().unwrap().unwrap();
        let i = of.get_output_index();
        let k = with.get_output_index();

        if of.clone().unwrap() == with.clone().unwrap() {
            if i == k {
                return Ok(of);
            }

            if Rc::strong_count(&unwrapped) > 4 {
                return Err(Error::DanglingReference(of.unwrap().nets().collect()));
            }
        } else if Rc::strong_count(&unwrapped) > 3 {
            return Err(Error::DanglingReference(of.unwrap().nets().collect()));
        }

        let old_index = of.get_operand();

        if let Some(nets) = self.outputs.borrow().get(&old_index)
            && nets.contains(&of.as_net())
        {
            if of.is_an_input() {
                return Err(Error::NonuniqueNets(nets.iter().cloned().collect()));
            } else {
                let id = of.as_net().get_identifier().clone() + "_replaced".into();
                of.as_net_mut().set_identifier(id);
            }
        }

        let new_index = with.get_operand();
        let objects = self.objects.borrow();
        for oref in objects.iter() {
            let operands = &mut oref.borrow_mut().operands;
            for operand in operands.iter_mut() {
                if let Some(op) = operand
                    && *op == old_index
                {
                    *operand = Some(new_index);
                }
            }
        }

        // Move all the old outputs to the new key
        let outs = self.outputs.borrow_mut().remove(&old_index);
        if let Some(outs) = outs {
            self.outputs
                .borrow_mut()
                .entry(new_index)
                .or_default()
                .extend(outs);
        }

        Ok(of)
    }
}

impl<I> Netlist<I>
where
    I: Instantiable,
{
    /// Returns the name of the netlist module
    pub fn get_name(&self) -> Ref<'_, String> {
        self.name.borrow()
    }

    /// Sets the name of the netlist module
    /// # Panics
    ///
    /// Panics if the module name cannot be borrowed mutably.
    pub fn set_name(&self, name: String) {
        *self.name.borrow_mut() = name;
    }

    /// Iterates over the input ports of the netlist.
    pub fn get_input_ports(&self) -> impl Iterator<Item = Net> {
        self.objects().filter_map(|oref| {
            if oref.is_an_input() {
                Some(oref.as_net().clone())
            } else {
                None
            }
        })
    }

    /// Returns a list of output nets
    pub fn get_output_ports(&self) -> Vec<Net> {
        self.outputs
            .borrow()
            .values()
            .flat_map(|nets| nets.iter().cloned())
            .collect()
    }

    /// Constructs an analysis of the netlist.
    pub fn get_analysis<'a, A: Analysis<'a, I>>(&'a self) -> Result<A, Error> {
        A::build(self)
    }

    /// Finds the first circuit node that drives the `net`. This operation is O(n).
    /// This should be unique provided the netlist is well-formed.
    pub fn find_net(&self, net: &Net) -> Option<DrivenNet<I>> {
        for obj in self.objects() {
            for o in obj.outputs() {
                if *o.as_net() == *net {
                    return Some(o);
                }
            }
        }
        None
    }

    /// Returns a `NetRef` to the first circuit node
    pub fn first(&self) -> Option<NetRef<I>> {
        self.objects
            .borrow()
            .first()
            .map(|nr| NetRef::wrap(nr.clone()))
    }

    /// Returns a `NetRef` to the last circuit node
    pub fn last(&self) -> Option<NetRef<I>> {
        self.objects
            .borrow()
            .last()
            .map(|nr| NetRef::wrap(nr.clone()))
    }

    /// Returns the number of objects in the netlist (instances + inputs)
    pub fn len(&self) -> usize {
        self.objects.borrow().len()
    }

    /// Returns `true` if the netlist contains no objects.
    pub fn is_empty(&self) -> bool {
        self.objects.borrow().is_empty()
    }

    /// Returns `true` if an output of `netref` which is driving a module output.
    ///
    /// # Panics
    /// The `netref` does not belong to this netlist
    pub fn drives_an_output(&self, netref: NetRef<I>) -> bool {
        self.belongs(&netref);
        let my_index = netref.unwrap().borrow().get_index();
        for key in self.outputs.borrow().keys() {
            if key.root() == my_index {
                return true;
            }
        }
        false
    }

    /// Rename nets and instances in the netlist using the provided *injective* function.
    /// Returns an error if the function is not injective.
    /// # Examples
    ///
    /// ```
    /// use safety_net::format_id;
    /// use safety_net::{Gate, GateNetlist};
    ///
    /// let netlist = GateNetlist::new("example".to_string());
    /// let inv = Gate::new_logical("INV".into(), vec!["A".into()], "Y".into());
    /// let foo = netlist.insert_input("foo".into());
    /// let nr = netlist.insert_gate(inv, "bar".into(), &[foo]).unwrap();
    /// nr.expose_with_name("baz".into());
    /// netlist.rename_nets(|id, i| format_id!("{}_{}", id, i) ).unwrap();
    /// // "bar_Y" -> "bar_Y_0"
    /// // "bar" -> "bar_1"
    /// ```
    pub fn rename_nets<F: Fn(&Identifier, usize) -> Identifier>(&self, f: F) -> Result<(), Error> {
        let mut i: usize = 0;
        for nr in self.objects() {
            if nr.is_an_input() {
                continue;
            }
            for mut net in nr.nets_mut() {
                let rename = f(net.get_identifier(), i);
                net.set_identifier(rename);
                i += 1;
            }
        }

        for nr in self.objects() {
            if nr.is_an_input() {
                continue;
            }

            let rename = f(&nr.get_instance_name().unwrap(), i);
            nr.set_instance_name(rename);
            i += 1;
        }

        self.verify()
    }

    /// Retains the [DrivenNet]s in `set`, given they are used. Otherwise, they are cleaned and returned in a `Ok(vec)`.
    pub fn retain_once(&self, set: &mut HashSet<DrivenNet<I>>) -> Result<Vec<Object<I>>, Error> {
        let mut dead_objs = HashSet::new();
        {
            let fan_out = self.get_analysis::<FanOutTable<I>>()?;
            for obj in self.objects() {
                let mut is_dead = true;
                for net in obj.outputs() {
                    // This should account for outputs
                    if fan_out.net_has_uses(&net.as_net()) {
                        is_dead = false;
                    } else {
                        set.remove(&net);
                    }
                }
                if is_dead && !obj.is_an_input() {
                    dead_objs.insert(obj.unwrap().borrow().index);
                }
            }
        }

        if dead_objs.is_empty() {
            return Ok(vec![]);
        }

        let old_objects = self.objects.take();

        // Check no dangling references will be created before mutating
        for i in dead_objs.iter() {
            let rc = &old_objects[*i];
            if Rc::strong_count(rc) > 1 {
                self.objects.replace(old_objects.clone());
                return Err(Error::DanglingReference(
                    rc.borrow().get().get_nets().to_vec(),
                ));
            }
        }

        let mut removed = Vec::new();
        let mut remap: HashMap<usize, usize> = HashMap::new();
        for (old_index, obj) in old_objects.into_iter().enumerate() {
            if dead_objs.contains(&old_index) {
                removed.push(obj.borrow().get().clone());
                continue;
            }

            let new_index = self.objects.borrow().len();
            remap.insert(old_index, new_index);
            obj.borrow_mut().index = new_index;
            self.objects.borrow_mut().push(obj);
        }

        for obj in self.objects.borrow().iter() {
            for operand in obj.borrow_mut().inds_mut() {
                let root = operand.root();
                let root = *remap.get(&root).unwrap_or(&root);
                *operand = operand.remap(root);
            }
        }

        let pairs: Vec<_> = self.outputs.take().into_iter().collect();
        for (operand, net) in pairs {
            let root = operand.root();
            let root = *remap.get(&root).unwrap_or(&root);
            let new_operand = operand.remap(root);
            self.outputs.borrow_mut().insert(new_operand, net);
        }

        Ok(removed)
    }

    /// Removes unused nodes from the netlist, until it stops changing.
    /// Returns `Ok(vec)` of the removed objects.
    pub fn clean(&self) -> Result<Vec<Object<I>>, Error> {
        let mut removed = Vec::new();
        let mut r = self.retain_once(&mut HashSet::new())?;
        while !r.is_empty() {
            removed.extend(r);
            r = self.retain_once(&mut HashSet::new())?;
        }
        Ok(removed)
    }

    /// Retains the [DrivenNet]s in `set`, given they are used. Otherwise, they are cleaned and returned in a `Ok(vec)`.
    pub fn retain(&self, set: &mut HashSet<DrivenNet<I>>) -> Result<Vec<Object<I>>, Error> {
        let mut removed = Vec::new();
        let mut r = self.retain_once(set)?;
        while !r.is_empty() {
            removed.extend(r);
            r = self.retain_once(set)?;
        }
        Ok(removed)
    }

    /// Returns `true` if all the nets/insts are uniquely named
    fn nets_insts_unique(&self) -> Result<(), Error> {
        let mut nets = HashSet::new();
        for net in self {
            if !nets.insert(net.clone().take_identifier()) {
                return Err(Error::NonuniqueNets(vec![net]));
            }
        }
        for inst in self.objects() {
            if let Some(name) = inst.get_instance_name()
                && !nets.insert(name.clone())
            {
                return Err(Error::NonuniqueInsts(vec![name]));
            }
        }
        Ok(())
    }

    fn connections_type_check(&self) -> Result<(), Error> {
        for conn in self.connections() {
            let target = *conn.target().get_port().get_type();
            let source = *conn.src().as_net().get_type();
            if target != source {
                return Err(Error::TypeError(conn.src().as_net().clone()));
            }
        }
        Ok(())
    }

    /// Verifies that a netlist is well-formed.
    pub fn verify(&self) -> Result<(), Error> {
        if self.outputs.borrow().is_empty() {
            return Err(Error::NoOutputs);
        }

        self.nets_insts_unique()?;
        self.connections_type_check()?;

        Ok(())
    }
}

/// Represent a driven net alongside its connection to an input port
#[derive(Debug, Clone)]
pub struct Connection<I: Instantiable> {
    driver: DrivenNet<I>,
    input: InputPort<I>,
}

impl<I> Connection<I>
where
    I: Instantiable,
{
    fn new(driver: DrivenNet<I>, input: InputPort<I>) -> Self {
        Self { driver, input }
    }

    /// Return the driver of the connection
    pub fn src(&self) -> DrivenNet<I> {
        self.driver.clone()
    }

    /// Return the net along the connection
    pub fn net(&self) -> Net {
        self.driver.as_net().clone()
    }

    /// Returns the input port of the connection
    pub fn target(&self) -> InputPort<I> {
        self.input.clone()
    }
}

impl<I> std::fmt::Display for Connection<I>
where
    I: Instantiable,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.net().fmt(f)
    }
}

/// Strategies for fast batching netlist rewrites
pub mod rewriter {
    use super::{DrivenNet, Error, Instantiable, NetRef, Netlist, Operand};
    use crate::graph::FanOutTable;
    use std::collections::HashMap;
    use std::rc::Rc;

    /// Uses a union-find to batch replacements in a netlist closer to O(n) time.
    /// The replacement only considers the uses of a net that existed at the time of creation of [NetMapper].
    /// Connections created after the creation of the [NetMapper] will not be replaced.
    pub struct NetMapper<'a, I: Instantiable> {
        parent: HashMap<DrivenNet<I>, DrivenNet<I>>,
        netlist: &'a Netlist<I>,
        fanout: FanOutTable<'a, I>,
    }

    impl<'a, I: Instantiable> NetMapper<'a, I> {
        /// Create a new empty mapper.
        pub fn new(netlist: &'a Netlist<I>) -> Result<Self, Error> {
            Ok(Self {
                parent: HashMap::new(),
                netlist,
                fanout: netlist.get_analysis::<FanOutTable<I>>()?,
            })
        }

        /// Get the final replacement for the net
        pub fn find(&self, x: DrivenNet<I>) -> DrivenNet<I> {
            let mut root = x;
            while let Some(p) = self.parent.get(&root) {
                root = p.clone();
            }
            root
        }

        /// Add a replacement to the mapper. Returns an error if the replacement creates a cycle.
        ///
        /// # Panics
        /// If `of` was already mapped to `with`
        pub fn replace(&mut self, of: DrivenNet<I>, with: DrivenNet<I>) -> DrivenNet<I> {
            let of_root = self.find(of.clone());
            let with_root = self.find(with);
            if of_root == with_root {
                panic!("Already mapped by NetMapper: {of}");
            }
            self.parent.insert(of_root, with_root);
            of
        }

        /// Apply the replacements to the netlist.
        /// Returns the nets that were replaced.
        pub fn apply(self) -> Result<Vec<DrivenNet<I>>, Error> {
            // Build the one-pass map
            let mut map: HashMap<Operand, Operand> = HashMap::new();
            for k in self.parent.keys().cloned() {
                let v = self.find(k.clone());
                if k != v {
                    map.insert(k.get_operand(), v.get_operand());
                }
            }

            drop(self.parent);

            // Check that replacements are all valid
            for (of, with) in map.iter() {
                let unwrapped = self.netlist.objects.borrow()[of.root()].clone();
                let i = of.secondary();
                let k = of.secondary();
                let nr = NetRef::wrap(unwrapped.clone());

                if of.root() == with.root() {
                    if i == k {
                        continue;
                    }

                    if Rc::strong_count(&unwrapped) - self.fanout.get_ref_count(&nr) > 4 {
                        return Err(Error::DanglingReference(nr.nets().collect()));
                    }
                } else if Rc::strong_count(&unwrapped) - self.fanout.get_ref_count(&nr) > 3 {
                    return Err(Error::DanglingReference(nr.nets().collect()));
                }

                let old_index = of;
                let of = DrivenNet::new(i, nr);

                if let Some(nets) = self.netlist.outputs.borrow().get(old_index)
                    && nets.contains(&of.as_net())
                {
                    if of.is_an_input() {
                        return Err(Error::NonuniqueNets(nets.iter().cloned().collect()));
                    } else {
                        let id = of.as_net().get_identifier().clone() + "_replaced".into();
                        of.as_net_mut().set_identifier(id);
                    }
                }
            }

            let objects = self.netlist.objects.borrow();
            for (of, &with) in map.iter() {
                let of = DrivenNet::new(of.secondary(), NetRef::wrap(objects[of.root()].clone()));
                for u in self.fanout.get_users(&of) {
                    let place = u.pos;
                    let u = u.unwrap().unwrap();
                    let operands = &mut u.borrow_mut().operands;
                    operands[place] = Some(with);
                }
            }

            for (of, &with) in map.iter() {
                // Move all the old outputs to the new key
                let outs = self.netlist.outputs.borrow_mut().remove(of);
                if let Some(outs) = outs {
                    self.netlist
                        .outputs
                        .borrow_mut()
                        .entry(with)
                        .or_default()
                        .extend(outs);
                }
            }

            let res: Vec<_> = map
                .into_keys()
                .map(|operand| {
                    DrivenNet::new(
                        operand.secondary(),
                        NetRef::wrap(self.netlist.objects.borrow()[operand.root()].clone()),
                    )
                })
                .collect();

            Ok(res)
        }
    }
}

/// A collection of iterators for the netlist
pub mod iter {

    use super::{
        Connection, DrivenNet, InputPort, Instantiable, Net, NetRef, Netlist, Operand, WeakIndex,
    };
    use std::collections::{HashMap, HashSet};
    /// An iterator over the nets in a netlist
    pub struct NetIterator<'a, I: Instantiable> {
        netlist: &'a Netlist<I>,
        index: usize,
        subindex: usize,
    }

    impl<'a, I> NetIterator<'a, I>
    where
        I: Instantiable,
    {
        /// Creates a new iterator for the netlist
        pub fn new(netlist: &'a Netlist<I>) -> Self {
            Self {
                netlist,
                index: 0,
                subindex: 0,
            }
        }
    }

    impl<I> Iterator for NetIterator<'_, I>
    where
        I: Instantiable,
    {
        type Item = Net;

        fn next(&mut self) -> Option<Self::Item> {
            while self.index < self.netlist.objects.borrow().len() {
                let objects = self.netlist.objects.borrow();
                let object = objects[self.index].borrow();
                if self.subindex < object.get().get_nets().len() {
                    let net = object.get().get_nets()[self.subindex].clone();
                    self.subindex += 1;
                    return Some(net);
                }
                self.subindex = 0;
                self.index += 1;
            }
            None
        }
    }

    /// An iterator over the objects in a netlist
    pub struct ObjectIterator<'a, I: Instantiable> {
        netlist: &'a Netlist<I>,
        index: usize,
    }

    impl<'a, I> ObjectIterator<'a, I>
    where
        I: Instantiable,
    {
        /// Creates a new  object iterator for the netlist
        pub fn new(netlist: &'a Netlist<I>) -> Self {
            Self { netlist, index: 0 }
        }
    }

    impl<I> Iterator for ObjectIterator<'_, I>
    where
        I: Instantiable,
    {
        type Item = NetRef<I>;

        fn next(&mut self) -> Option<Self::Item> {
            if self.index < self.netlist.objects.borrow().len() {
                let objects = self.netlist.objects.borrow();
                let object = &objects[self.index];
                self.index += 1;
                return Some(NetRef::wrap(object.clone()));
            }
            None
        }
    }

    /// An iterator over the connections in a netlist
    pub struct ConnectionIterator<'a, I: Instantiable> {
        netlist: &'a Netlist<I>,
        index: usize,
        subindex: usize,
    }

    impl<'a, I> ConnectionIterator<'a, I>
    where
        I: Instantiable,
    {
        /// Create a new connection iterator for the netlist
        pub fn new(netlist: &'a Netlist<I>) -> Self {
            Self {
                netlist,
                index: 0,
                subindex: 0,
            }
        }
    }

    impl<I> Iterator for ConnectionIterator<'_, I>
    where
        I: Instantiable,
    {
        type Item = super::Connection<I>;

        fn next(&mut self) -> Option<Self::Item> {
            while self.index < self.netlist.objects.borrow().len() {
                let objects = self.netlist.objects.borrow();
                let object = objects[self.index].borrow();
                let noperands = object.operands.len();
                while self.subindex < noperands {
                    if let Some(operand) = &object.operands[self.subindex] {
                        let driver = match operand {
                            Operand::DirectIndex(idx) => {
                                DrivenNet::new(0, NetRef::wrap(objects[*idx].clone()))
                            }
                            Operand::CellIndex(idx, j) => {
                                DrivenNet::new(*j, NetRef::wrap(objects[*idx].clone()))
                            }
                        };
                        let input = InputPort::new(
                            self.subindex,
                            NetRef::wrap(objects[self.index].clone()),
                        );
                        self.subindex += 1;
                        return Some(Connection::new(driver, input));
                    }
                    self.subindex += 1;
                }
                self.subindex = 0;
                self.index += 1;
            }
            None
        }
    }

    /// A stack that can check contains in roughly O(1) time.
    #[derive(Clone)]
    struct Walk<T: std::hash::Hash + PartialEq + Eq + Clone> {
        stack: Vec<T>,
        counter: HashMap<T, usize>,
    }

    impl<T> Walk<T>
    where
        T: std::hash::Hash + PartialEq + Eq + Clone,
    {
        /// Create a new, empty Stack.
        fn new() -> Self {
            Self {
                stack: Vec::new(),
                counter: HashMap::new(),
            }
        }

        /// Inserts an element into the stack
        fn push(&mut self, item: T) {
            self.stack.push(item.clone());
            *self.counter.entry(item).or_insert(0) += 1;
        }

        /// Returns true if the stack shows a cycle
        fn contains_cycle(&self) -> bool {
            self.counter.values().any(|&count| count > 1)
        }

        /// Returns true if the stack contains a cycle to the root node
        fn root_cycle(&self) -> bool {
            if self.stack.is_empty() {
                return false;
            }
            self.counter[&self.stack[0]] > 1
        }

        /// Returns a reference to the last element in the stack
        fn last(&self) -> Option<&T> {
            self.stack.last()
        }
    }

    /// A depth-first iterator over the circuit nodes in a netlist
    /// # Examples
    ///
    /// ```
    /// use safety_net::iter::DFSIterator;
    /// use safety_net::GateNetlist;
    ///
    /// let netlist = GateNetlist::new("example".to_string());
    /// netlist.insert_input("input1".into());
    /// let mut nodes = Vec::new();
    /// let mut dfs = DFSIterator::new(&netlist, netlist.last().unwrap());
    /// while let Some(n) = dfs.next() {
    ///     if dfs.check_cycles() {
    ///         panic!("Cycle detected in the netlist");
    ///     }
    ///     nodes.push(n);
    /// }
    /// ```
    pub struct DFSIterator<'a, I: Instantiable> {
        dfs: NetDFSIterator<'a, I>,
        seen: HashSet<NetRef<I>>,
    }

    impl<'a, I> DFSIterator<'a, I>
    where
        I: Instantiable,
    {
        /// Create a new DFS iterator for the netlist starting at `from`.
        pub fn new(netlist: &'a Netlist<I>, from: NetRef<I>) -> Self {
            Self {
                dfs: NetDFSIterator::new(netlist, DrivenNet::new(0, from)),
                seen: HashSet::new(),
            }
        }
    }

    impl<I> DFSIterator<'_, I>
    where
        I: Instantiable,
    {
        /// Check if the DFS traversal has encountered a cycle yet.
        pub fn check_cycles(&self) -> bool {
            self.dfs.check_cycles()
        }

        /// Consumes the iterator to detect cycles in the netlist.
        pub fn detect_cycles(self) -> bool {
            self.dfs.detect_cycles()
        }

        /// Check if the DFS traversal has encountered the root `from`` again.
        pub fn check_self_loop(&self) -> bool {
            self.dfs.check_self_loop()
        }

        /// Consumes the iterator to detect if the DFS traversal will encounter the root `from` again.
        pub fn detect_self_loop(self) -> bool {
            self.dfs.detect_self_loop()
        }
    }

    impl<I> Iterator for DFSIterator<'_, I>
    where
        I: Instantiable,
    {
        type Item = NetRef<I>;

        fn next(&mut self) -> Option<Self::Item> {
            let d = self.dfs.next()?;
            if self.seen.insert(d.clone().unwrap()) {
                Some(d.unwrap())
            } else {
                self.next()
            }
        }
    }

    type TermFn<I> = Box<dyn Fn(&DrivenNet<I>) -> bool + 'static>;

    /// Depth-first iterator that works like DFSIterator but iterates over DrivenNet
    pub struct NetDFSIterator<'a, I: Instantiable> {
        netlist: &'a Netlist<I>,
        stacks: Vec<Walk<DrivenNet<I>>>,
        visited: HashSet<usize>,
        visited_net: HashSet<(usize, usize)>,
        any_cycle: bool,
        root_cycle: bool,
        terminate: TermFn<I>,
    }

    impl<'a, I> NetDFSIterator<'a, I>
    where
        I: Instantiable,
    {
        /// Create a new DFS DrivenNet iterator for the netlist starting at `from`, ignoring all dependencies beyond the `terminate` condition.
        /// Terminators themselves *are* included in the iteration.
        pub fn new_filtered<F: Fn(&DrivenNet<I>) -> bool + 'static>(
            netlist: &'a Netlist<I>,
            from: DrivenNet<I>,
            terminate: F,
        ) -> Self {
            let mut s = Walk::new();
            s.push(from);
            Self {
                netlist,
                stacks: vec![s],
                visited: HashSet::new(),
                visited_net: HashSet::new(),
                any_cycle: false,
                root_cycle: false,
                terminate: Box::new(terminate),
            }
        }

        /// Create a new DFS DrivenNet iterator for the netlist starting at `from`.
        pub fn new(netlist: &'a Netlist<I>, from: DrivenNet<I>) -> Self {
            Self::new_filtered(netlist, from, |_| false)
        }
    }

    impl<I> NetDFSIterator<'_, I>
    where
        I: Instantiable,
    {
        /// Check if the DFS traversal has encountered a cycle yet.
        pub fn check_cycles(&self) -> bool {
            self.any_cycle
        }

        /// Consumes the iterator to detect cycles in the netlist.
        pub fn detect_cycles(mut self) -> bool {
            if self.any_cycle {
                return true;
            }

            while let Some(_) = self.next() {
                if self.any_cycle {
                    return true;
                }
            }

            self.any_cycle
        }

        /// Check if the DFS traversal has encountered the root `from` again.
        pub fn check_self_loop(&self) -> bool {
            self.root_cycle
        }

        /// Consumes the iterator to detect if the DFS traversal will encounter the root `from` again.
        pub fn detect_self_loop(mut self) -> bool {
            if self.root_cycle {
                return true;
            }

            while let Some(_) = self.next() {
                if self.root_cycle {
                    return true;
                }
            }

            self.root_cycle
        }
    }

    impl<I> Iterator for NetDFSIterator<'_, I>
    where
        I: Instantiable,
    {
        type Item = DrivenNet<I>;

        fn next(&mut self) -> Option<Self::Item> {
            if let Some(walk) = self.stacks.pop() {
                self.any_cycle |= walk.contains_cycle();
                self.root_cycle |= walk.root_cycle();
                let item = walk.last().cloned();
                let uw = item.clone().unwrap().unwrap().unwrap();
                let index = uw.borrow().get_index();
                let secondary = item.as_ref().unwrap().pos;
                if self.visited.insert(index) {
                    if !(self.terminate)(item.as_ref().unwrap()) {
                        let operands = &uw.borrow().operands;
                        for operand in operands.iter().flatten() {
                            let mut new_walk = walk.clone();
                            new_walk.push(DrivenNet::new(
                                operand.secondary(),
                                NetRef::wrap(self.netlist.index_weak(&operand.root())),
                            ));
                            self.stacks.push(new_walk);
                        }
                    }
                    self.visited_net.insert((index, secondary));
                    return item;
                }

                if self.visited_net.insert((index, secondary)) {
                    return item;
                }

                return self.next();
            }

            None
        }
    }
}

impl<'a, I> IntoIterator for &'a Netlist<I>
where
    I: Instantiable,
{
    type Item = Net;
    type IntoIter = iter::NetIterator<'a, I>;

    fn into_iter(self) -> Self::IntoIter {
        iter::NetIterator::new(self)
    }
}

/// Filter invariants of [Instantiable] in a netlist. Use it like you would `matches!`.
/// Example: ```filter_nodes!(netlist, Gate::AND(_));```
#[macro_export]
macro_rules! filter_nodes {
    ($netlist:ident, $pattern:pat $(if $guard:expr)? $(,)?) => {
        $netlist.matches(|f| match f {
            $pattern $(if $guard)? => true,
            _ => false
        })
    };
}

impl<I> Netlist<I>
where
    I: Instantiable,
{
    /// Returns an iterator over the circuit nodes in the netlist.
    pub fn objects(&self) -> impl Iterator<Item = NetRef<I>> {
        iter::ObjectIterator::new(self)
    }

    /// Returns an iterator over the circuit nodes that match the instance type.
    pub fn matches<F>(&self, filter: F) -> impl Iterator<Item = NetRef<I>>
    where
        F: Fn(&I) -> bool,
    {
        self.objects().filter(move |f| {
            if let Some(inst_type) = f.get_instance_type() {
                filter(&inst_type)
            } else {
                false
            }
        })
    }

    /// Returns an iterator to principal inputs in the netlist as references.
    pub fn inputs(&self) -> impl Iterator<Item = DrivenNet<I>> {
        self.objects()
            .filter(|n| n.is_an_input())
            .map(|n| DrivenNet::new(0, n))
    }

    /// Returns an iterator to circuit nodes that drive an output in the netlist.
    pub fn outputs(&self) -> Vec<(DrivenNet<I>, Net)> {
        self.outputs
            .borrow()
            .iter()
            .flat_map(|(k, nets)| {
                nets.iter().map(|n| {
                    (
                        DrivenNet::new(k.secondary(), NetRef::wrap(self.index_weak(&k.root()))),
                        n.clone(),
                    )
                })
            })
            .collect()
    }

    /// Returns an iterator over the wire connections in the netlist.
    pub fn connections(&self) -> impl Iterator<Item = Connection<I>> {
        iter::ConnectionIterator::new(self)
    }

    /// Returns a depth-first search iterator over the nodes in the netlist.
    ///
    /// # Panics
    /// `from` does not belong to this netlist
    pub fn node_dfs(&self, from: NetRef<I>) -> impl Iterator<Item = NetRef<I>> {
        self.belongs(&from);
        iter::DFSIterator::new(self, from)
    }

    /// Returns a depth-first search iterator over the nodes in the netlist, with the nodes in DrivenNet form.
    ///
    /// # Panics
    /// `from` does not belong to this netlist
    pub fn net_dfs(&self, from: DrivenNet<I>) -> impl Iterator<Item = DrivenNet<I>> {
        self.belongs(&from.clone().unwrap());
        iter::NetDFSIterator::new(self, from)
    }

    #[cfg(feature = "serde")]
    /// Serializes the netlist to a writer.
    pub fn serialize(self, writer: impl std::io::Write) -> Result<(), serde_json::Error>
    where
        I: ::serde::Serialize,
    {
        serde::netlist_serialize(self, writer)
    }

    #[cfg(feature = "graph")]
    /// Converts the current configuration of the netlist to a graphviz string
    pub fn dot_string(&self) -> Result<String, Error> {
        use super::graph::{Edge, MultiDiGraph, Node};
        use petgraph::dot::{Config, Dot};
        use petgraph::graph::{DiGraph, EdgeReference, NodeIndex};
        let analysis = self.get_analysis::<MultiDiGraph<_>>()?;
        let graph = analysis.get_graph();

        fn node_impl<I: Instantiable>(
            _graph: &DiGraph<Node<I, String>, Edge<I, Net>>,
            node: (NodeIndex, &Node<I, String>),
        ) -> String {
            let n = node.1;
            let mut attr = String::new();

            match n {
                Node::NetRef(nr) if nr.get_instance_type().is_some() => attr += "shape=record, ",
                _ => attr += "shape=ellipse, ",
            }

            match n {
                Node::NetRef(nr)
                    if let Some(inst_type) = nr.get_instance_type()
                        && !inst_type.is_driverless() =>
                {
                    let mut record = "{ { ".to_string();

                    let l = nr.get_num_input_ports();
                    for (i, port) in nr.inputs().enumerate() {
                        let id = port.get_port().get_identifier().clone();
                        record += &format!("{{ <{}> {} }}", id, id);

                        if i != l - 1 {
                            record += " | ";
                        }
                    }

                    record += &format!(
                        " }} | {}({}) }}",
                        inst_type.get_name(),
                        nr.get_instance_name().unwrap()
                    );
                    attr += &format!("label=\"{record}\"");
                }
                _ => attr += &format!("label=\"{n}\""),
            }

            attr
        }

        fn edge_impl<I: Instantiable>(
            _graph: &DiGraph<Node<I, String>, Edge<I, Net>>,
            edge: EdgeReference<Edge<I, Net>>,
        ) -> String {
            match edge.weight() {
                Edge::Connection(c) => {
                    format!(", port=\"{}\"", c.target().get_port().get_identifier())
                }
                _ => String::new(),
            }
        }

        let dot = Dot::with_attr_getters(
            graph,
            &[Config::NodeNoLabel],
            &edge_impl::<I>,
            &node_impl::<I>,
        );

        // Post-process to add port specifiers to the edges.
        let mut result = String::new();
        for line in dot.to_string().lines() {
            if line.contains("->") && line.contains("port=") {
                let port = line
                    .split("port=\"")
                    .nth(1)
                    .unwrap()
                    .split('"')
                    .next()
                    .unwrap();
                let (l, r) = line.split_once("->").unwrap();
                let (l, r) = (l, r.trim());
                let (d, r) = r.split_once(" ").unwrap();
                result += &format!("{l}-> {d}:{port} {r}\n");
            } else {
                result += line;
                result += "\n";
            }
        }

        Ok(result)
    }

    #[cfg(feature = "graph")]
    /// Dumps the current netlist to <module_name>.dot in the current working directory.
    pub fn dump_dot(&self) -> std::io::Result<()> {
        use std::io::Write;
        let mut dir = std::env::current_dir()?;
        let mod_name = format!("{}.dot", self.get_name());
        dir.push(mod_name);
        let mut file = std::fs::File::create(dir)?;
        if let Err(e) = self.verify() {
            write!(file, "Netlist verification failed: {e}")
        } else {
            let dot = self.dot_string().unwrap();
            write!(file, "{dot}")
        }
    }
}

impl<I> std::fmt::Display for Netlist<I>
where
    I: Instantiable,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        // Borrow everything first
        let objects = self.objects.borrow();
        let outputs = self.outputs.borrow();

        writeln!(f, "module {} (", self.get_name())?;

        // Print inputs and outputs
        let level = 2;
        let indent = " ".repeat(level);
        for oref in objects.iter() {
            let owned = oref.borrow();
            let obj = owned.get();
            if let Object::Input(net) = obj {
                writeln!(f, "{}{},", indent, net.get_identifier().emit_name())?;
            }
        }

        // Flatten the outputs to collect all (operand, net) pairs
        let all_outputs: Vec<_> = outputs.values().flat_map(|nets| nets.iter()).collect();
        for (i, net) in all_outputs.iter().enumerate() {
            if i == all_outputs.len() - 1 {
                writeln!(f, "{}{}", indent, net.get_identifier().emit_name())?;
            } else {
                writeln!(f, "{}{},", indent, net.get_identifier().emit_name())?;
            }
        }
        writeln!(f, ");")?;

        // Make wire decls
        let mut already_decl = HashSet::new();
        for oref in objects.iter() {
            let owned = oref.borrow();
            let obj = owned.get();
            if let Object::Input(net) = obj {
                writeln!(f, "{}input {};", indent, net.get_identifier().emit_name())?;
                writeln!(f, "{}wire {};", indent, net.get_identifier().emit_name())?;
                already_decl.insert(net.clone());
            }
        }
        for nets in outputs.values() {
            for net in nets {
                if !already_decl.contains(net) {
                    writeln!(f, "{}output {};", indent, net.get_identifier().emit_name())?;
                    writeln!(f, "{}wire {};", indent, net.get_identifier().emit_name())?;
                    already_decl.insert(net.clone());
                }
            }
        }
        for oref in objects.iter() {
            let owned = oref.borrow();
            let obj = owned.get();
            if let Object::Instance(nets, _, inst_type) = obj
                && inst_type.get_constant().is_none()
            {
                for net in nets.iter() {
                    if !already_decl.contains(net) {
                        writeln!(f, "{}wire {};", indent, net.get_identifier().emit_name())?;
                        already_decl.insert(net.clone());
                    }
                }
            }
        }

        for oref in objects.iter() {
            let owned = oref.borrow();
            let obj = owned.get();

            // Skip emitting constants as their uses will be hard-wired
            if let Some(inst_type) = obj.get_instance_type()
                && inst_type.get_constant().is_some()
            {
                continue;
            }

            if let Object::Instance(nets, inst_name, inst_type) = obj {
                for (k, v) in owned.attributes.iter() {
                    if let Some(value) = v {
                        writeln!(f, "{indent}(* {k} = \"{value}\" *)")?;
                    } else {
                        writeln!(f, "{indent}(* {k} *)")?;
                    }
                }

                write!(f, "{}{} ", indent, inst_type.get_name())?;
                if inst_type.is_parameterized() {
                    writeln!(f, "#(")?;
                    let level = 4;
                    let indent = " ".repeat(level);
                    let params: Vec<_> = inst_type.parameters().collect();
                    for (i, (k, v)) in params.iter().enumerate() {
                        if i == params.len() - 1 {
                            writeln!(f, "{indent}.{k}({v})")?;
                        } else {
                            writeln!(f, "{indent}.{k}({v}),")?;
                        }
                    }
                    let level = 2;
                    let indent = " ".repeat(level);
                    write!(f, "{indent}) ")?;
                }
                writeln!(f, "{} (", inst_name.emit_name())?;
                let level = 4;
                let indent = " ".repeat(level);
                for (idx, port) in inst_type.get_input_ports().into_iter().enumerate() {
                    let port_name = port.get_identifier().emit_name();
                    if let Some(operand) = owned.operands[idx].as_ref() {
                        let operand_net = match operand {
                            Operand::DirectIndex(idx) => objects[*idx].borrow().as_net().clone(),
                            Operand::CellIndex(idx, j) => {
                                objects[*idx].borrow().get_net(*j).clone()
                            }
                        };

                        let operand_str = if let Some(inst_type) =
                            objects[operand.root()].borrow().get().get_instance_type()
                            && let Some(logic) = inst_type.get_constant()
                        {
                            logic.to_string()
                        } else {
                            operand_net.get_identifier().emit_name()
                        };

                        writeln!(f, "{}.{}({}),", indent, port_name, operand_str)?;
                    }
                }

                for (idx, net) in nets.iter().enumerate() {
                    let port_name = inst_type.get_output_port(idx).get_identifier().emit_name();
                    if idx == nets.len() - 1 {
                        writeln!(
                            f,
                            "{}.{}({})",
                            indent,
                            port_name,
                            net.get_identifier().emit_name()
                        )?;
                    } else {
                        writeln!(
                            f,
                            "{}.{}({}),",
                            indent,
                            port_name,
                            net.get_identifier().emit_name()
                        )?;
                    }
                }

                let level = 2;
                let indent = " ".repeat(level);
                writeln!(f, "{indent});")?;
            }
        }

        for (driver, nets) in outputs.iter() {
            for net in nets {
                let driver_net = match driver {
                    Operand::DirectIndex(idx) => self.index_weak(idx).borrow().as_net().clone(),
                    Operand::CellIndex(idx, j) => self.index_weak(idx).borrow().get_net(*j).clone(),
                };

                let driver_str = if let Some(inst_type) = self
                    .index_weak(&driver.root())
                    .borrow()
                    .get()
                    .get_instance_type()
                    && let Some(logic) = inst_type.get_constant()
                {
                    logic.to_string()
                } else {
                    driver_net.get_identifier().emit_name()
                };

                if net.get_identifier() != driver_net.get_identifier() {
                    writeln!(
                        f,
                        "{}assign {} = {};",
                        indent,
                        net.get_identifier().emit_name(),
                        driver_str
                    )?;
                }
            }
        }

        writeln!(f, "endmodule")
    }
}

/// A type alias for a netlist of gates
pub type GateNetlist = Netlist<Gate>;
/// A type alias to Gate circuit nodes
pub type GateRef = NetRef<Gate>;

#[cfg(test)]
mod tests {
    use super::iter::{DFSIterator, NetDFSIterator};
    use super::*;
    #[test]
    fn test_delete_netlist() {
        let netlist = Netlist::new("simple_example".to_string());

        // Add the the two inputs
        let input1 = netlist.insert_input("input1".into());
        let input2 = netlist.insert_input("input2".into());

        // Instantiate an AND gate
        let instance = netlist
            .insert_gate(
                Gate::new_logical("AND".into(), vec!["A".into(), "B".into()], "Y".into()),
                "my_and".into(),
                &[input1.clone(), input2.clone()],
            )
            .unwrap();

        // Make this AND gate an output
        let instance = instance.expose_as_output().unwrap();
        instance.delete_uses().unwrap();
        // We can still clean this mostly empty netlist
        assert!(netlist.clean().is_ok());
        input1.expose_with_name("an_output".into());
        assert!(netlist.clean().is_ok());
    }

    #[test]
    #[should_panic(expected = "Attempted to create a gate with a sliced identifier")]
    fn gate_w_slice_panics() {
        Gate::new_logical("AND[1]".into(), vec!["A".into(), "B".into()], "Y".into());
    }

    #[test]
    fn gates_dont_have_params() {
        // The baseline implementation of gates do not have parameters.
        let gate = Gate::new_logical("AND".into(), vec!["A".into(), "B".into()], "Y".into());
        assert!(!gate.has_parameter(&"id".into()));
        assert!(gate.get_parameter(&"id".into()).is_none());
        assert_eq!(*gate.get_gate_name(), "AND".into());
    }

    #[test]
    fn operand_conversions() {
        let operand = Operand::CellIndex(3, 2);
        assert_eq!(operand.to_string(), "3.2");
        let parsed = "3.2".parse::<Operand>();
        assert!(parsed.is_ok());
        let parsed = parsed.unwrap();
        assert_eq!(operand, parsed);
    }

    #[test]
    #[should_panic(expected = "out of bounds for netref")]
    fn test_bad_output() {
        let netlist = GateNetlist::new("min_module".to_string());
        let a = netlist.insert_input("a".into());
        DrivenNet::new(1, a.unwrap());
    }

    #[test]
    fn test_netdfsiterator() {
        let netlist = Netlist::new("dfs_netlist".to_string());

        // inputs
        let a = netlist.insert_input("a".into());
        let b = netlist.insert_input("b".into());
        let c = netlist.insert_input("c".into());
        let d = netlist.insert_input("d".into());
        let e = netlist.insert_input("e".into());

        // gates
        let n1 = netlist
            .insert_gate(
                Gate::new_logical("OR".into(), vec!["A".into(), "B".into()], "Y".into()),
                "n1".into(),
                &[a.clone(), b.clone()],
            )
            .unwrap()
            .get_output(0);
        let n2 = netlist
            .insert_gate(
                Gate::new_logical("NOR".into(), vec!["A".into(), "B".into()], "Y".into()),
                "n2".into(),
                &[d.clone(), e.clone()],
            )
            .unwrap()
            .get_output(0);
        let n3 = netlist
            .insert_gate(
                Gate::new_logical("AND".into(), vec!["A".into(), "B".into()], "Y".into()),
                "n3".into(),
                &[n1.clone(), c.clone()],
            )
            .unwrap()
            .get_output(0);
        let n4 = netlist
            .insert_gate(
                Gate::new_logical("NAND".into(), vec!["A".into(), "B".into()], "Y".into()),
                "n4".into(),
                &[n3.clone(), n2.clone()],
            )
            .unwrap()
            .get_output(0);
        n4.clone().expose_with_name("y".into());

        // test DFSIterator
        let mut dfs = NetDFSIterator::new(&netlist, n4.clone());
        assert_eq!(dfs.next(), Some(n4));
        assert_eq!(dfs.next(), Some(n2));
        assert_eq!(dfs.next(), Some(e));
        assert_eq!(dfs.next(), Some(d));
        assert_eq!(dfs.next(), Some(n3));
        assert_eq!(dfs.next(), Some(c));
        assert_eq!(dfs.next(), Some(n1));
        assert_eq!(dfs.next(), Some(b));
        assert_eq!(dfs.next(), Some(a));
        assert_eq!(dfs.next(), None);
    }

    #[test]
    fn test_dfs_cycles() {
        let netlist = Netlist::new("dfs_cycles".to_string());

        // inputs
        let a = netlist.insert_input("a".into());

        // gates
        let and = netlist.insert_gate_disconnected(
            Gate::new_logical("AND".into(), vec!["A".into(), "B".into()], "Y".into()),
            "and".into(),
        );

        // connect and form cycle
        a.connect(and.get_input(0));
        and.get_output(0).connect(and.get_input(1));

        // test dfs iterators
        let dfs = DFSIterator::new(&netlist, and.clone());
        let driven_dfs = NetDFSIterator::new(&netlist, and.get_output(0));

        assert!(dfs.detect_cycles());
        assert!(driven_dfs.detect_cycles());
    }

    #[test]
    fn test_netdfsiterator_with_boundary() {
        let netlist = Netlist::new("dfs_netlist".to_string());

        // inputs
        let a = netlist.insert_input("a".into());
        let b = netlist.insert_input("b".into());
        let c = netlist.insert_input("c".into());
        let d = netlist.insert_input("d".into());
        let e = netlist.insert_input("e".into());

        // gates
        let n1 = netlist
            .insert_gate(
                Gate::new_logical("OR".into(), vec!["A".into(), "B".into()], "Y".into()),
                "n1".into(),
                &[a.clone(), b.clone()],
            )
            .unwrap()
            .get_output(0);
        let n2 = netlist
            .insert_gate(
                Gate::new_logical("NOR".into(), vec!["A".into(), "B".into()], "Y".into()),
                "n2".into(),
                &[d.clone(), e.clone()],
            )
            .unwrap()
            .get_output(0);
        let n3 = netlist
            .insert_gate(
                Gate::new_logical("AND".into(), vec!["A".into(), "B".into()], "Y".into()),
                "n3".into(),
                &[n1.clone(), c.clone()],
            )
            .unwrap()
            .get_output(0);
        let n4 = netlist
            .insert_gate(
                Gate::new_logical("NAND".into(), vec!["A".into(), "B".into()], "Y".into()),
                "n4".into(),
                &[n3.clone(), n2.clone()],
            )
            .unwrap()
            .get_output(0);

        // Stop DFS expansion at n3 to emulate a traversal boundary.
        let n3_boundary = n3.clone();
        let mut dfs =
            NetDFSIterator::new_filtered(&netlist, n4.clone(), move |n| *n == n3_boundary);
        assert_eq!(dfs.next(), Some(n4));
        assert_eq!(dfs.next(), Some(n2));
        assert_eq!(dfs.next(), Some(e));
        assert_eq!(dfs.next(), Some(d));
        assert_eq!(dfs.next(), Some(n3));
        assert_eq!(dfs.next(), None);
    }

    #[test]
    fn test_dfs_convergence() {
        let netlist = GateNetlist::new("example".to_string());
        let gate = Gate::new_logical_multi(
            "FA".into(),
            vec!["A".into(), "B".into()],
            vec!["S".into(), "COUT".into()],
        );
        let a = netlist.insert_input("a".into());
        let b = netlist.insert_input("b".into());
        let gate = netlist.insert_gate(gate, "g".into(), &[a, b]).unwrap();
        let s = gate.get_output(0);
        let c = gate.get_output(1);
        let gate = Gate::new_logical("AND".into(), vec!["A".into(), "B".into()], "Y".into());
        let d = netlist.insert_gate(gate, "h".into(), &[s, c]).unwrap();

        let dfs = NetDFSIterator::new(&netlist, d.get_output(0));
        let c = dfs.count();
        assert_eq!(c, 5);

        let dfs = DFSIterator::new(&netlist, d.clone());
        let c = dfs.count();
        assert_eq!(c, 4);
    }
}
#[cfg(feature = "serde")]
/// Serde support for netlists
pub mod serde {
    use super::{Netlist, Operand, OwnedObject, WeakIndex};
    use crate::{
        attribute::{AttributeKey, AttributeValue},
        circuit::{Instantiable, Net, Object},
    };
    use serde::{Deserialize, Serialize, de::DeserializeOwned};
    use std::cell::RefCell;
    use std::{
        collections::{BTreeSet, HashMap},
        rc::Rc,
    };

    #[derive(Debug, Serialize, Deserialize)]
    struct SerdeObject<I>
    where
        I: Instantiable + Serialize,
    {
        /// The object that is owned by the netlist
        object: Object<I>,
        /// The list of operands for the object
        operands: Vec<Option<Operand>>,
        /// A collection of attributes for the object
        attributes: HashMap<AttributeKey, AttributeValue>,
    }

    impl<I, O> From<OwnedObject<I, O>> for SerdeObject<I>
    where
        I: Instantiable + Serialize,
        O: WeakIndex<usize, Output = OwnedObject<I, O>>,
    {
        fn from(value: OwnedObject<I, O>) -> Self {
            SerdeObject {
                object: value.object,
                operands: value.operands,
                attributes: value.attributes,
            }
        }
    }

    impl<I> SerdeObject<I>
    where
        I: Instantiable + Serialize,
    {
        fn into_owned_object<O>(self, owner: &Rc<O>, index: usize) -> OwnedObject<I, O>
        where
            O: WeakIndex<usize, Output = OwnedObject<I, O>>,
        {
            OwnedObject {
                object: self.object,
                owner: Rc::downgrade(owner),
                operands: self.operands,
                attributes: self.attributes,
                index,
            }
        }
    }

    #[derive(Debug, Serialize, Deserialize)]
    struct SerdeNetlist<I>
    where
        I: Instantiable + Serialize,
    {
        /// The name of the netlist
        name: String,
        /// The list of objects in the netlist, such as inputs, modules, and primitives
        objects: Vec<SerdeObject<I>>,
        /// The list of operands that point to objects which are outputs.
        /// Indices must be a string if we want to support JSON.
        /// Each operand can map to multiple nets, supporting output aliases.
        outputs: HashMap<String, BTreeSet<Net>>,
    }

    impl<I> From<Netlist<I>> for SerdeNetlist<I>
    where
        I: Instantiable + Serialize,
    {
        fn from(value: Netlist<I>) -> Self {
            SerdeNetlist {
                name: value.name.into_inner(),
                objects: value
                    .objects
                    .into_inner()
                    .into_iter()
                    .map(|o| {
                        Rc::try_unwrap(o)
                            .ok()
                            .expect("Cannot serialize with live references")
                            .into_inner()
                            .into()
                    })
                    .collect(),
                outputs: value
                    .outputs
                    .into_inner()
                    .into_iter()
                    // Indices must be a string if we want to support JSON.
                    .map(|(o, nets)| (o.to_string(), nets.into_iter().collect()))
                    .collect(),
            }
        }
    }

    impl<I> SerdeNetlist<I>
    where
        I: Instantiable + Serialize,
    {
        /// Convert the serialized netlist back into a reference-counted netlist.
        fn into_netlist(self) -> Rc<Netlist<I>> {
            let netlist = Netlist::new(self.name);
            let outputs: HashMap<Operand, BTreeSet<Net>> = self
                .outputs
                .into_iter()
                .map(|(k, v)| {
                    let operand = k.parse::<Operand>().expect("Invalid index");
                    (operand, v.into_iter().collect())
                })
                .collect();
            let objects = self
                .objects
                .into_iter()
                .enumerate()
                .map(|(i, o)| {
                    let owned_object = o.into_owned_object(&netlist, i);
                    Rc::new(RefCell::new(owned_object))
                })
                .collect::<Vec<_>>();
            {
                let mut objs_mut = netlist.objects.borrow_mut();
                *objs_mut = objects;
                let mut outputs_mut = netlist.outputs.borrow_mut();
                *outputs_mut = outputs;
            }
            netlist
        }
    }

    /// Serialize the netlist into the writer.
    pub fn netlist_serialize<I: Instantiable + Serialize>(
        netlist: Netlist<I>,
        writer: impl std::io::Write,
    ) -> Result<(), serde_json::Error> {
        let sobj: SerdeNetlist<I> = netlist.into();
        serde_json::to_writer_pretty(writer, &sobj)
    }

    /// Deserialize a netlist from the reader.
    pub fn netlist_deserialize<I: Instantiable + Serialize + DeserializeOwned>(
        reader: impl std::io::Read,
    ) -> Result<Rc<Netlist<I>>, serde_json::Error> {
        let sobj: SerdeNetlist<I> = serde_json::from_reader(reader)?;
        Ok(sobj.into_netlist())
    }
}