netlistdb 0.3.1

use super::*;
use either::Either;

/// Direction provider trait.
///
/// Downstream databases (e.g., Liberty library or LEF/DEF library)
/// should implement this to provide pin direction information
/// used in constructing NetlistDB.
pub trait DirectionProvider {
    /// This function is called from NetlistDB constructor to
    /// query the direction of library cell pins.
    fn direction_of(
        &self,
        macro_name: &Substr,
        pin_name: &Substr, pin_idx: Option<isize>
    ) -> Direction;

    /// This function allows downstream databases to specify
    /// whether there should be a warning on unspecified
    /// directions when building netlist.
    #[inline]
    fn should_warn_missing_directions(&self) -> bool {
        true
    }
}

impl DirectionProvider for HashMap<(Substr, Substr, Option<isize>), Direction> {
    #[inline]
    fn direction_of(
        &self,
        macro_name: &Substr,
        pin_name: &Substr, pin_idx: Option<isize>
    ) -> Direction {
        let k = (macro_name.clone(), pin_name.clone(), pin_idx);
        self.get(&k).copied().unwrap_or(Direction::Unknown)
    }
}

impl<T> DirectionProvider for T
where T: Fn(&Substr, &Substr, Option<isize>) -> Direction {
    #[inline]
    fn direction_of(
        &self,
        macro_name: &Substr,
        pin_name: &Substr, pin_idx: Option<isize>
    ) -> Direction {
        self(macro_name, pin_name, pin_idx)
    }
}

/// A special direction hint that gives no answer to every pin.
/// This is useful if you do not care about the pin direction
/// (e.g. if you are outputting the benchmark statistics only).
pub struct NoDirection();

impl DirectionProvider for NoDirection {
    #[inline]
    fn direction_of(&self,
                    _: &Substr, _: &Substr, _: Option<isize>
    ) -> Direction {
        Direction::Unknown
    }

    /// Directions are explicitly ignored, so disable all
    /// such warnings.
    #[inline]
    fn should_warn_missing_directions(&self) -> bool {
        false
    }
}

impl NetlistDB {
    /// Get or insert a logic pin with hier, name and index.
    /// If exists, return index. Otherwise, add it and return it.
    #[inline]
    fn get_or_insert_logic_pin(
        &mut self, hier: &HierName, name: &Substr, idx: Option<isize>
    ) -> usize {
        let k = (hier.clone(), name.clone(), idx);
        if let Some(i) = self.logicpinname2id.get(&k) {
            return *i
        }
        let id = self.num_logic_pins;
        self.num_logic_pins += 1;
        self.logicpinname2id.insert(k.clone(), id);
        self.logicpintypes.push(LogicPinType::Others);
        self.logicpinnames.push(k);
        id
    }

    /// Find the logic pin with a specific name.
    /// If not found, *prints an error message* and returns None.
    /// This is useful in netlist construction.
    #[inline]
    #[must_use]
    fn try_find_logic_pin(
        &self, hier: &HierName, name: &Substr, idx: Option<isize>
    ) -> Option<usize> {
        let k = (hier.clone(), name.clone(), idx);
        let r = self.logicpinname2id.get(&k);
        if r.is_none() {
            clilog::error!(
                NL_SV_REF, "pin/net reference {}/{} [{:?}] not found",
                hier, name, idx);
        }
        r.copied()
    }

    /// Insert a cell with hier name and macro name.
    /// Returns the new cell id.
    #[inline]
    fn insert_cell(
        &mut self, hier: HierName, macro_name: Substr
    ) -> usize {
        let id = self.num_cells;
        self.num_cells += 1;
        self.cellname2id.insert(hier.clone(), id);
        self.celltypes.push(macro_name);
        self.cellnames.push(hier);
        id
    }

    /// Recursively build (and flatten) the hierarchical modules.
    /// `net_sets` is the disjoint set of logic pins into nets.
    /// `hier` is the current hier name.
    /// This call will build all port pins inside it. So no need to
    /// build them outside.
    #[must_use]
    fn build_modules(
        &mut self,
        modules: &HashMap<Substr, (SVerilogModule, ModuleMap)>,
        (_m_name, m, mm): (&Substr, &SVerilogModule, &ModuleMap),
        net_sets: &mut DisjointSet,
        hier: HierName
    ) -> Option<()> {
        // create nets/IO logic pins
        for def in &m.defs {
            for w in enum_in_width(def.width) {
                let id = self.get_or_insert_logic_pin(&hier, &def.name, w);
                self.logicpintypes[id] = LogicPinType::Net;
                // for the top module, the ports are tagged as
                // LogicPinType::TopPort outside the first invocation.
                // (in [NetlistDB::from_sverilog]).
            }
        }

        #[must_use]
        fn pin_assign_literal(
            net_sets: &mut DisjointSet, l: usize, c: u8
        ) -> Option<()> {
            match c {
                0 => net_sets.set_value(l, false),
                1 => net_sets.set_value(l, true),
                2 => {
                    clilog::error!(NL_SV_LIT, "X literal unsupported");
                    return None
                },
                3 => {},
                _ => unreachable!()
            }
            Some(())
        }

        // create named ports
        for (name, expr) in m.ports.iter().filter_map(|p| match p {
            SVerilogPortDef::Basic(_) => None,
            SVerilogPortDef::Conn(name, expr) => Some((name, expr))
        }) {
            let width = mm.port_widths.get(name).copied();
            for (id, eb) in enum_in_width(width).zip(mm.eval_expr(expr)) {
                let port_id = self.get_or_insert_logic_pin(&hier, name, id);
                use ExprBit::*;
                match eb {
                    Const(c) => {
                        pin_assign_literal(net_sets, port_id, c)?;
                    },
                    Var(pname, pidx) => {
                        let pin_id = self.try_find_logic_pin(
                            &hier, &pname, pidx)?;
                        net_sets.merge(port_id, pin_id);
                    }
                }
            }
        }

        let hier_prev = match hier.is_empty() {
            true => None,
            false => Some(Arc::new(hier.clone()))
        };

        // recurse into submodules and cells
        for cell in &m.cells {
            let new_hier = HierName {
                prev: hier_prev.clone(),
                cur: cell.cell_name.clone()
            };

            // build submodule/cell and get ranges of ports
            let (is_leaf, ioport_ranges) = match modules.get(&cell.macro_name) {
                Some((m, mm)) => {
                    // non-leaf.
                    self.build_modules(
                        modules,
                        (&cell.macro_name, m, mm),
                        net_sets,
                        new_hier.clone()
                    )?;
                    (false,
                     Either::Left(cell.ioports.iter().map(|(name, _)| {
                         mm.port_widths.get(name.as_str()).copied()
                     })))
                },
                None => {
                    // leaf cell.
                    self.insert_cell(new_hier.clone(),
                                     cell.macro_name.clone());
                    (true,
                     Either::Right(cell.ioports.iter().map(|(_, expr)| {
                         // mimics CadXX InnoXX:
                         // a leaf cell port is a scalar iff width == 1.
                         match mm.eval_expr_len(expr) {
                             1 => None,
                             w @ _ => Some(SVerilogRange(0, w as isize - 1))
                         }
                     })))
                }
            };

            // connect edges.
            for (w, (name, expr)) in ioport_ranges.zip(cell.ioports.iter()) {
                for (i, eb) in enum_in_width(w).zip(mm.eval_expr(expr)) {
                    let id = match is_leaf {
                        // if it is a leaf, we insert the pin.
                        true => self.get_or_insert_logic_pin(&new_hier, &name, i),
                        // if it is a submodule, the pin should already be ready,
                        // so we assert its existence.
                        false => self.try_find_logic_pin(&new_hier, &name, i)?
                    };
                    if is_leaf {
                        self.logicpintypes[id] = LogicPinType::LeafCellPin;
                    }
                    match eb {
                        ExprBit::Const(c) => {
                            pin_assign_literal(net_sets, id, c)?;
                        }
                        ExprBit::Var(pname, pidx) => {
                            // a wire might be used but not defined.
                            let eb_id = self.get_or_insert_logic_pin(
                                &hier, &pname, pidx);
                            let typ = &mut self.logicpintypes[eb_id];
                            if *typ == LogicPinType::Others {
                                *typ = LogicPinType::Net;
                            }
                            net_sets.merge(id, eb_id);
                        }
                    }
                }
            }
        }
        
        // connect assignments
        for assign in &m.assigns {
            let len_lhs = mm.eval_expr_len(&assign.lhs);
            let len_rhs = mm.eval_expr_len(&assign.rhs);
            if len_lhs != len_rhs {
                clilog::error!(
                    NL_SV_INCOMP,
                    "incompatible assign width for `{}`: \
                     len(LHS) = {}, len(RHS) = {}",
                    assign, len_lhs, len_rhs);
                return None
            }

            for (lb, rb) in mm.eval_expr(&assign.lhs).zip(
                mm.eval_expr(&assign.rhs)
            ) {
                use ExprBit::*;
                match (lb, rb) {
                    (Var(nl, il), Var(nr, ir)) => {
                        let l = self.get_or_insert_logic_pin(&hier, &nl, il);
                        let r = self.get_or_insert_logic_pin(&hier, &nr, ir);
                        net_sets.merge(l, r);
                    }
                    (Var(nl, il), Const(c)) => {
                        let l = self.get_or_insert_logic_pin(&hier, &nl, il);
                        pin_assign_literal(net_sets, l, c)?;
                    }
                    (Const(c), Var(nr, ir)) => {
                        let r = self.get_or_insert_logic_pin(&hier, &nr, ir);
                        pin_assign_literal(net_sets, r, c)?;
                    }
                    _ => {
                        clilog::error!(NL_SV_LIT, "Bad lit-lit assign.");
                        return None;
                    }
                }
            }
        }

        Some(())
    }

    /// Building a netlist database STEP 1: initialize most of the
    /// graph structure using parsed verilog modules starting from
    /// the top-level module.
    /// 
    /// The only remaining thing to do is to assign pin directions.
    ///
    /// Splitting this out would possibly reduce the code bloat
    /// caused by the polymorphic DirectionProvider.
    /// (This is a premature optimization. Evil.)
    fn init_graph_from_modules(
        modules: &HashMap<Substr, (SVerilogModule, ModuleMap)>,
        (top_name, top_m, top_mm): (&Substr, &SVerilogModule, &ModuleMap),
    ) -> Option<NetlistDB> {
        let (est_num_cells, est_num_logic_pins) = estimate_size(
            modules, &mut HashSet::new(), (top_name, top_m, top_mm),
            &mut HashMap::new()
        )?;
        let est_num_cells = est_num_cells + 1; // top level

        let mut db = NetlistDB {
            name: top_name.clone(),
            num_cells: 1,
            num_pins: 0,
            num_logic_pins: 0,
            num_nets: 0,
            cellname2id: HashMap::with_capacity(est_num_cells), 
            logicpinname2id: HashMap::with_capacity(est_num_logic_pins),
            pinname2id: HashMap::new(),
            netname2id: HashMap::new(),
            celltypes: Vec::with_capacity(est_num_cells),
            cellnames: Vec::with_capacity(est_num_cells),
            logicpintypes: Vec::with_capacity(est_num_logic_pins),
            logicpinnames: Vec::with_capacity(est_num_logic_pins),
            pinid2logicpinid: Vec::new(),
            pinnames: Vec::new(),
            pin2cell: UVec::new(),
            pin2net: UVec::new(),
            cell2pin: Default::default(),
            net2pin: Default::default(),
            pindirect: UVec::new(),
            net_zero: None,
            net_one: None
        };

        db.cellname2id.insert(HierName::empty(), 0);
        db.celltypes.push(top_name.clone());
        db.cellnames.push(HierName::empty());

        let mut net_sets = DisjointSet::with_capacity(est_num_logic_pins);

        db.build_modules(
            modules, (top_name, top_m, top_mm),
            &mut net_sets, HierName::empty()
        )?;

        if db.num_logic_pins > est_num_logic_pins {
            clilog::warn!(
                NL_SV_MOREPIN,
                "there turns out to be more \
                 logic pin (net) than expected -- typically because there \
                 are nets undefined but used. It is not suggested to do so \
                 because this will lead to long construction time.");
        }

        // set TopPort property for top module ports.
        for port in &top_m.ports {
            let name = match port {
                SVerilogPortDef::Basic(name) => name,
                SVerilogPortDef::Conn(name, _) => name
            };
            let w = top_mm.port_widths.get(name).copied();
            for w in enum_in_width(w) {
                let id = db.try_find_logic_pin(&HierName::empty(), name, w)?;
                db.logicpintypes[id] = LogicPinType::TopPort;
            }
        }

        // create net maps.
        // first finalize the disjoint set and compute the sizes.
        let (num_nets, logicpin2nets, net_zero, net_one) =
            net_sets.finalize(db.num_logic_pins)?;
        db.num_nets = num_nets;
        db.net_zero = net_zero;
        db.net_one = net_one;

        // finalize pin index and pin-net mapping.
        db.pinid2logicpinid = db.logicpintypes.iter()
            .enumerate()
            .filter_map(|(id, t)| {
                match t.is_pin() {
                    false => None,
                    true => Some(id)
                }
            })
            .collect::<Vec<usize>>();
        db.num_pins = db.pinid2logicpinid.len();

        db.pinname2id = db.pinid2logicpinid.iter()
            .enumerate()
            .map(|(id, logic_id)|
                 (db.logicpinnames[*logic_id].clone(), id))
            .collect();

        db.pinnames = db.pinid2logicpinid.iter()
            .map(|logic_id| db.logicpinnames[*logic_id].clone())
            .collect();

        db.pin2net = db.pinid2logicpinid.iter()
            .map(|logic_id| logicpin2nets[*logic_id])
            .collect();

        // finalize pin to cell map
        db.pin2cell = unsafe {
            UVec::new_uninitialized(db.num_pins, Device::CPU)
        };
        db.pin2cell.fill(usize::MAX);
        for ((hier, _, _), id) in &db.pinname2id {
            db.pin2cell[*id] = *db.cellname2id.get(hier).unwrap();
        }
        debug_assert!(!db.pin2cell.iter().any(|x| *x == usize::MAX));

        // build net names
        db.netname2id = db.logicpinnames.iter()
            .enumerate()
            .filter_map(|(id, name)| match db.logicpintypes[id].is_net() {
                false => None,
                true => Some((name.clone(), logicpin2nets[id]))
            })
            .collect();
        
        // construct CSR
        db.cell2pin = VecCSR::from(db.num_cells, db.num_pins, &db.pin2cell);
        db.net2pin = VecCSR::from(db.num_nets, db.num_pins, &db.pin2net);
        Some(db)
    }

    /// Build a database from structural verilog source code.
    /// 
    /// The top module to be built from can be optionally specified through
    /// the `top` parameter.
    ///
    /// There should be a way to specify library pin directions --
    /// through a trait called direction provider.
    pub fn from_sverilog(
        sverilog_source: ArcStr,
        top: Option<&str>,
        direction_provider: &impl DirectionProvider
    ) -> Option<NetlistDB> {
        let SVerilog{modules} = match SVerilog::parse_str(sverilog_source) {
            Ok(sv) => sv,
            Err(err) => {
                clilog::error!(
                    NL_SV_PARSE, "Error parsing the verilog netlist: {}", err);
                return None
            }
        };
        
        let modules: HashMap<Substr, (SVerilogModule, ModuleMap)> =
            modules.into_iter().map(|(k, v)| {
                let mm = ModuleMap::from(&v);
                (k, (v, mm))
            }).collect();
        
        let (top_name, top_m, top_mm) = find_top_module(&modules, top)?;
        
        let mut db = NetlistDB::init_graph_from_modules(
            &modules,
            (top_name, top_m, top_mm)
        )?;

        db.assign_direction((top_name, top_m, top_mm), direction_provider)?;
        
        Some(db)
    }

    /// Building a netlist database STEP 2:
    /// Assign directions to netlist pins given the macro and the pin type.
    #[must_use]
    fn assign_direction(
        &mut self,
        (_top_name, top_m, top_mm): (&Substr, &SVerilogModule, &ModuleMap),
        lib: &impl DirectionProvider
    ) -> Option<()> {
        // query the provider for cell pins
        self.pindirect = self.pinid2logicpinid.iter()
            .enumerate()
            .map(|(i, logic_id)| {
                match self.logicpintypes[*logic_id] {
                    LogicPinType::TopPort => Direction::Unknown,
                    LogicPinType::LeafCellPin => {
                        let macro_name = &self.celltypes[self.pin2cell[i]];
                        let pin_name = &self.pinnames[i];
                        lib.direction_of(
                            macro_name, &pin_name.1, pin_name.2)
                    }
                    _ => unreachable!()
                }
            })
            .collect();

        // query the module definition for ports
        for port in &top_m.ports {
            use ExprBit::*;
            let (name, ref_names) = match port {
                SVerilogPortDef::Basic(name) => {
                    (name, Either::Left(std::iter::repeat(name)))
                }
                SVerilogPortDef::Conn(name, expr) => {
                    (name, Either::Right(
                        top_mm.eval_expr(expr).map(|eb| match eb {
                            Const(_) => {
                                clilog::error!(NL_SV_LIT, "Literal unsupported");
                                panic!() // for simplicity here.
                            }
                            Var(pname, _) => pname
                        })
                    ))
                }
            };
            let width = top_mm.port_widths.get(name).copied();
            for (id, ref_name) in enum_in_width(width).zip(ref_names) {
                let k = (HierName::empty(), name.clone(), id);
                let deftype = match top_mm.def_types.get(ref_name) {
                    Some(v) => v,
                    None => {
                        clilog::error!(
                            NL_SV_REF, "io reference {}/{}{:?} not found,\
                                        required for direction discovery.",
                            k.0, k.1, k.2);
                        return None
                    }
                };
                use WireDefType::*;
                use Direction::*;
                let dir = match deftype {
                    Input => O,  // input port is net output.
                    Output => I,
                    InOut => {
                        clilog::error!(NL_SV_INOUT, "inout unsupported");
                        return None
                    }
                    Wire => {
                        clilog::error!(
                            NL_SV_REF, "named port connection {} should \
                                        not refer to non-io wire {}.",
                            name, ref_name);
                        return None
                    }
                };
                self.pindirect[*self.pinname2id.get(&k).unwrap()] = dir;
            }
        }

        let num_unknowns = self.pindirect.iter()
            .filter(|t| **t == Direction::Unknown)
            .count();

        if num_unknowns != 0 && lib.should_warn_missing_directions() {
            clilog::warn!(NL_SV_DIRUNK, "There are {} pins with unknown \
                                         directions",
                          num_unknowns);
        }

        let mut num_undriven_nets = 0;

        // todo: parallelizable
        for i in 0..self.num_nets {
            let l = self.net2pin.start[i];
            let r = self.net2pin.start[i + 1];
            let outs = (l..r).zip(self.net2pin.items[l..r].iter())
                .filter_map(
                    |(i, x)| if self.pindirect[*x] == Direction::O { Some(i) } else { None }
                )
                .collect::<Vec<usize>>();
            if outs.len() == 0 {
                // if this net is not intended to be constant,
                // we report the error.
                if Some(i) != self.net_zero &&
                    Some(i) != self.net_one
                {
                    num_undriven_nets += 1;
                }
                continue;
            }
            if outs.len() != 1 {
                clilog::error!(
                    NL_SV_NETIO,
                    "There must be exactly one driver for each net. \
                     The net {} has outputs {:?}",
                    i, outs);
                return None
            }
            let p = outs[0];
            self.net2pin.items.swap(l, p);
        }

        if num_undriven_nets != 0 && lib.should_warn_missing_directions() {
            clilog::warn!(NL_SV_NETIO_UNDRIV,
                          "There are {} nets without driving pins.",
                          num_undriven_nets);
        }
        
        Some(())
    }

    /// Convenient shortcut to read from file.
    /// The parameters are similar to [NetlistDB::from_sverilog].
    pub fn from_sverilog_file(
        sverilog_source_path: impl AsRef<std::path::Path>,
        top: Option<&str>,
        direction_provider: &impl DirectionProvider
    ) -> Option<NetlistDB> {
        let p = sverilog_source_path.as_ref();
        let s = match std::fs::read_to_string(p) {
            Ok(s) => s,
            Err(e) => {
                clilog::error!(NL_IO, "read sverilog file {} failed: {}",
                               p.display(), e);
                return None
            }
        };
        NetlistDB::from_sverilog(ArcStr::from(s), top, direction_provider)
    }
}