libreda_sta/

lib.rs

// SPDX-FileCopyrightText: 2021-2024 Thomas Kramer <code@tkramer.ch>
// SPDX-License-Identifier: AGPL-3.0-or-later

//! # == this crate is experimental and not stable for now ==
//! Incremental graph-based static timing analysis (STA) for the LibrEDA framework.
//!
//! Timing analysis is performed on netlist data structures that implement the
//! [`trait@NetlistBase`] trait. This makes the STA algorithm easily portable.
//!
//! The concept of timing, delays and constraints is abstracted by a set of [`traits`].
//! This architecture should allow to implement simple timing models such as the non-linear delay model (NLDM)
//! and more complicated models (such as statistical models) in a consistent way.
//!

#![deny(missing_docs)]
#![deny(unused_imports)]

mod clock_definition;
mod cone_propagation;
mod critical_path;
mod graphviz;
mod interp;
mod levelization;
/// Public modules
pub mod liberty_library;
mod lowest_common_ancestor;
pub mod models;
mod signal_propagation;
pub mod traits;

pub use clock_definition::ClockDefinition;
use libreda_logic::traits::LogicOps;
use models::clock_tag::ClockAwareModel;
use models::clock_tag::ClockId;
use petgraph::visit::IntoNodeReferences;
use traits::cell_logic_model::LogicModel;
/// Public exports.
pub use traits::timing_library::*;
use traits::*;

mod liberty_util;
mod timing_graph;

use crate::models::clock_tag::ClockAwareInterconnectModel;
use crate::models::clock_tag::SignalWithClock;
use crate::models::zero_interconnect_delay::ZeroInterconnectDelayModel;
use crate::signal_propagation::propagate_signals_incremental;
use pargraph::BorrowDataCell;

use libreda_db::netlist::prelude::TerminalId;
use libreda_db::prelude as db;
use libreda_db::reference_access::*;
use libreda_db::traits::*;
use num_traits::Zero;
use std::fmt::Debug;

use crate::traits::{CellConstraintModel, CellDelayModel, CellLoadModel};
use fnv::{FnvHashMap, FnvHashSet};

pub(crate) const PATH_SEPARATOR: &str = ":";

/// Analysis mode.
/// * `Hold`: Check for hold violations.
/// * `Setup`: Check for setup violations.
#[derive(Copy, Clone, Debug, Hash, Eq, PartialEq)]
pub enum StaMode {
    /// Hold analysis mode. Find shortest paths. Early mode.
    Early,
    /// Setup analysis mode. Find longest paths. Late mode.
    Late,
}

/// Compute total net capacitances for each net of the top circuit.
/// Simply sums up the input capacitances of all connected input pins for each net.
fn compute_net_loads<N: NetlistBase, Lib: CellLoadModel<N>>(
    top: &CellRef<N>,
    library: Lib,
) -> FnvHashMap<N::NetId, Lib::Load> {
    log::debug!(
        "compute load capacitances of all nets ({})",
        top.num_internal_nets()
    );

    let static_input_signals = None;

    // Compute all output load capacitances.
    let net_capacitances: FnvHashMap<_, _> = top
        .each_net()
        // Compute the capacitance of the net.
        .map(|net| {
            // Sum up all gate capacitances attached to this net.
            let total_capacitance = net
                .each_pin_instance()
                .map(|pin_inst| {
                    let pin = pin_inst.pin();
                    library.input_pin_load(&pin.id(), &|_| static_input_signals)
                })
                .fold(library.zero(), |cap, acc| library.sum_loads(&cap, &acc));

            (net.id(), total_capacitance)
        })
        .collect();
    net_capacitances
}

/// Error during static timing analysis.
/// This includes errors in the liberty library, mismatches between netlist and library
/// or invalid netlists (drive conflicts, etc).
#[derive(Debug, Clone)]
pub enum StaError {
    /// Pin is referenced in the library but not present in the netlist.
    PinNotFoundInNetlist(String, String),
    /// Some cells used in the netlist cannot be found in the liberty library.
    MissingCellsInLiberty(Vec<String>),
    /// Something is bad with the netlist. This includes drive conflicts,
    /// floating input pins, etc.
    BadNetlist,
    /// Circuit contains a combinational cycle.
    CombinationalCycle,
    /// Unspecified error.
    Other(String),
}

impl std::fmt::Display for StaError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            StaError::PinNotFoundInNetlist(cell, pin) =>
                write!(f, "Pin '{}' in cell '{}' is referenced in liberty library but not present in the netlist.",
                       pin, cell),
            StaError::MissingCellsInLiberty(cell_names) =>
                write!(f, "Cells could not be found in liberty library: {}", cell_names.join(", ")),
            StaError::BadNetlist => write!(f, "Something is not good with the netlist. See log for more details."),
            StaError::CombinationalCycle => write!(f, "Circuit contains a combinational cycle. See log for more details."),
            StaError::Other(msg) => write!(f, "STA error: {}", msg),
        }
    }
}

/// Simple static timing analysis engine.
#[derive(Debug)]
pub struct SimpleSTA<N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + LoadBase + ConstraintBase,
{
    /// Netlist (or reference to the netlist) which contains the circuit to be analyzed.
    netlist: N,
    /// ID of the circuit which should be analyzed.
    top_cell: N::CellId,
    /// Timing-library, enhanced with clock-awareness.
    cell_model: ClockAwareModel<Lib>,
    /// Set to `true` iff the library has not been checked for consistency yet.
    /// This is set to `true` again when cells are added to the circuit.
    need_check_library: bool,
    /// User-specified input signals.
    input_signals: FnvHashMap<(N::PinId, RiseFall), SignalWithClock<Lib::Signal>>,
    /// User-specified loads.
    output_loads: FnvHashMap<N::PinId, Lib::Load>,
    /// Constraints for output signals.
    required_output_signals: FnvHashMap<(N::PinId, RiseFall), SignalWithClock<Lib::RequiredSignal>>,
    clocks: FnvHashMap<TerminalId<N>, ClockDefinition<Lib::Signal>>,
    /// Internal representation of the timing graph.
    /// This is constructed from the netlist and kept up-to-date during incremental
    /// changes of the netlist.
    timing_graph: timing_graph::TimingGraph<N, ClockAwareModel<Lib>>,
    /// Count the number of timing updates.
    /// Used to efficiently mark nodes in the timing graph which are relevant for the current
    /// incremental upgrade.
    /// Used to distinguish between the first full update (needs more initialization) and
    /// subsequent incremental updates.
    generation: u32,
}

/// Reference to STA engine in timed state.
#[derive(Debug)]
pub struct Timed<'a, N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + LoadBase + ConstraintBase,
{
    inner: &'a SimpleSTA<N, Lib>,
}

impl<'a, N, Lib> std::ops::Deref for Timed<'a, N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + LoadBase + ConstraintBase,
{
    type Target = SimpleSTA<N, Lib>;

    fn deref(&self) -> &Self::Target {
        self.inner
    }
}

impl<'a, N, Lib> Timed<'a, N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + LoadBase + ConstraintBase,
{
    /// For testing only.
    pub fn report_clock(&self, pin: TerminalId<N>, edge_polarity: RiseFall) -> Option<ClockId> {
        self.timing_graph
            .get_terminal_data(&pin, edge_polarity)
            .and_then(|d| d.signal.as_ref().and_then(|s| s.clock_id()))
    }

    /// Report longest or shortest paths.
    pub fn report_critical_paths(&self, clock_id: ClockId, setup_hold: SetupHold) -> () {
        todo!()
    }
}

impl<N, Lib> SimpleSTA<N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
}

impl<N, Lib> SimpleSTA<N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
    /// Get ownership of the netlist data.
    pub fn into_inner(self) -> N {
        self.netlist
    }

    /// Shortcut to get the reference to the netlist.
    fn netlist(&self) -> &N {
        &self.netlist
    }

    fn top_cell_ref(&self) -> CellRef<N> {
        self.netlist().cell_ref(&self.top_cell)
    }
}

/// Argument type for `set_input_signal`.
/// This way of passing arguments allows to add other optional data without breaking API changes.
#[derive(Copy, Clone, Debug, Hash, Eq, PartialEq)]
pub struct InputSignal<S> {
    signal: SignalWithClock<S>,
}

impl<S> InputSignal<S> {
    /// Create a new input signal argument from a signal.
    pub fn new(signal: S) -> Self {
        Self {
            signal: SignalWithClock::new(signal),
        }
    }

    /// Associate the input signal with a clock.
    pub fn with_clock(mut self, clock_id: Option<ClockId>) -> Self {
        self.signal = self.signal.with_clock_id(clock_id);
        self
    }
}

/// Argument type for `set_required_signal`.
/// This way of passing arguments allows to add other optional data without breaking API changes.
#[derive(Copy, Clone, Debug, Hash, Eq, PartialEq)]
pub struct RequiredSignalArg<S> {
    signal: SignalWithClock<S>,
}

impl<S> RequiredSignalArg<S> {
    /// Create a new input signal argument from a signal.
    pub fn new(signal: S) -> Self {
        Self {
            signal: SignalWithClock::new(signal),
        }
    }

    /// Associate the input signal with a clock.
    pub fn with_clock(mut self, clock_id: Option<ClockId>) -> Self {
        self.signal = self.signal.with_clock_id(clock_id);
        self
    }
}

impl<N, Lib> SimpleSTA<N, Lib>
where
    N: db::NetlistBaseMT,
    Lib: CellLoadModel<N> + CellDelayModel<N> + CellConstraintModel<N> + LogicModel<N> + Sync,
    Lib::LogicValue: LogicOps + From<bool> + TryInto<bool>,
{
    /// Compute the timing information.
    /// On success, returns the STA engine in [`TimingAvailable`] mode where
    /// timing queries are enabled.
    /// On error, returns a tuple with an error code and the STA engine in [`Modifiable`] mode.
    pub fn update_timing(&mut self) -> Result<Timed<'_, N, Lib>, StaError> {
        // Compute the timing.

        match self.run_sta() {
            Ok(_) => Ok(Timed { inner: self }),
            Err(err) => Err(err),
        }
    }
}

impl<N, Lib> SimpleSTA<N, Lib>
where
    N: NetlistBase,
    Lib: CellLoadModel<N> + CellDelayModel<N> + CellConstraintModel<N> + LogicModel<N>,
    Lib::LogicValue: LogicOps + From<bool> + TryInto<bool>,
{
    /// Create a new static timing analysis engine which analyzes the given netlist
    /// using timing information of the cells from the given library.
    pub fn new(
        netlist: N,
        top_cell: N::CellId,
        cell_timing_library: Lib,
    ) -> Result<Self, StaError> {
        let mut sta = Self {
            top_cell,
            netlist,
            need_check_library: false,
            input_signals: Default::default(),
            output_loads: Default::default(),
            required_output_signals: Default::default(),
            clocks: Default::default(),
            timing_graph: timing_graph::TimingGraph::new(),
            generation: 0,
            cell_model: ClockAwareModel::new(cell_timing_library),
        };

        sta.init()?;

        Ok(sta)
    }

    fn init(&mut self) -> Result<(), StaError> {
        self.check_library()?;
        self.build_timing_graph()?;

        Ok(())
    }

    /// Set the signal at a primary input.
    ///
    /// # Typical usages
    /// * Set the input delay
    /// * Set the input slew
    pub fn set_input_signal(
        &mut self,
        primary_input: N::PinId,
        signal: InputSignal<Lib::Signal>,
    ) -> Result<(), StaError> {
        let transition_type = signal.signal.transition_type();

        let input_terminal = db::TerminalId::PinId(primary_input.clone());

        match transition_type {
            SignalTransitionType::Constant(_) => {
                self.timing_graph
                    .add_terminal_to_frontier(&input_terminal, Some(RiseFall::Rise));
                self.input_signals.insert(
                    (primary_input.clone(), RiseFall::Rise),
                    signal.signal.clone(),
                );
                self.timing_graph
                    .add_terminal_to_frontier(&input_terminal, Some(RiseFall::Fall));
                self.input_signals
                    .insert((primary_input, RiseFall::Fall), signal.signal);
            }
            SignalTransitionType::Rise => {
                self.timing_graph
                    .add_terminal_to_frontier(&input_terminal, Some(RiseFall::Rise));
                self.input_signals
                    .insert((primary_input, RiseFall::Rise), signal.signal);
            }
            SignalTransitionType::Fall => {
                self.timing_graph
                    .add_terminal_to_frontier(&input_terminal, Some(RiseFall::Fall));
                self.input_signals
                    .insert((primary_input, RiseFall::Fall), signal.signal);
            }
            SignalTransitionType::Any => {
                // Use the same input signal (delay/slew) for rising and falling edges.
                use SignalTransitionType::{Fall, Rise};
                for edge in [Rise, Fall] {
                    let mut s = signal.clone();
                    s.signal = s.signal.with_transition_type(edge);
                    self.set_input_signal(primary_input.clone(), s)?;
                }
            }
        }

        Ok(())
    }

    /// Set the load attached to a primary output.
    pub fn set_output_load(
        &mut self,
        primary_output: N::PinId,
        load: Lib::Load,
    ) -> Result<(), StaError> {
        self.timing_graph
            .add_terminal_to_frontier(&db::TerminalId::PinId(primary_output.clone()), None);

        self.output_loads.insert(primary_output, load);
        Ok(())
    }

    /// Specify the timing constraint of a primary output.
    pub fn set_required_output_signal(
        &mut self,
        primary_output: N::PinId,
        required_signal: RequiredSignalArg<Lib::RequiredSignal>,
    ) -> Result<(), StaError> {
        // TODO: Add only the necessary nodes to the frontier. Now we add both for rise and fall.
        let edge_type = None;
        self.timing_graph
            .add_terminal_to_frontier(&db::TerminalId::PinId(primary_output.clone()), edge_type);

        // TODO
        self.required_output_signals.insert(
            (primary_output.clone(), RiseFall::Rise),
            required_signal.signal.clone(),
        );
        self.required_output_signals
            .insert((primary_output, RiseFall::Fall), required_signal.signal);
        Ok(())
    }

    /// Specify a clock source.
    pub fn create_clock(
        &mut self,
        clock_pin: TerminalId<N>,
        mut clock_definition: ClockDefinition<Lib::Signal>,
    ) -> Result<ClockId, StaError> {
        assert_eq!(
            clock_definition.rising_edge.transition_type(),
            SignalTransitionType::Rise,
            "rising clock edge has wrong transition type"
        );
        assert_eq!(
            clock_definition.falling_edge.transition_type(),
            SignalTransitionType::Fall,
            "falling clock edge has wrong transition type"
        );

        let jitter = uom::si::f64::Time::zero(); // TODO

        // Create an ID of the clock. This ID is a single integer used to efficiently annotate nodes
        // in the timing graph.
        let clock_id = self
            .cell_model
            .create_primary_clock(clock_definition.period, jitter);

        clock_definition.clock_id = Some(clock_id);

        self.timing_graph.add_terminal_to_frontier(&clock_pin, None);

        // Set clock ID for an existing signal clock signals
        for edge_polarity in [RiseFall::Fall, RiseFall::Rise] {
            if let Some(mut node_data) = self
                .timing_graph
                .get_terminal_data_mut(&clock_pin, edge_polarity)
            {
                if let Some(s) = node_data.signal.as_mut() {
                    s.set_clock_id(Some(clock_id));
                }
            }
        }
        self.clocks.insert(clock_pin, clock_definition);

        Ok(clock_id)
    }

    /// Create graph of delay arcs.
    fn build_timing_graph(&mut self) -> Result<(), StaError> {
        log::debug!("create timing graph");
        self.timing_graph = timing_graph::TimingGraph::<_, _>::build_from_netlist(
            &self.top_cell_ref(),
            &self.cell_model,
            &self.cell_model,
        )?;

        Ok(())
    }

    /// Copy the defined input signals into the nodes of the timing graph.
    fn init_input_signals(&mut self) -> Result<(), StaError> {
        log::debug!("set input signals");
        for ((pin, edge_polarity), input_signal) in &self.input_signals {
            // Ignore defined input signals which are not part of the netlist.
            let terminal = db::TerminalId::PinId(pin.clone());

            self.timing_graph
                .add_terminal_to_frontier(&terminal, Some(*edge_polarity));

            if let Some(&[node_rise, node_fall]) = self.timing_graph.term2node.get(&terminal) {
                let node = match edge_polarity {
                    RiseFall::Rise => node_rise,
                    RiseFall::Fall => node_fall,
                };

                let terminal_ref = self.netlist().terminal_ref(&terminal);
                log::debug!(
                    "Set input signal for {}: {:?}",
                    terminal_ref.qname(PATH_SEPARATOR),
                    input_signal
                );

                let mut node_data = self
                    .timing_graph
                    .get_node_data_mut(node)
                    .expect("failed to get node data");

                node_data.signal = Some(input_signal.clone());
                node_data.is_primary_input = true;
            }
        }

        Ok(())
    }

    /// Copy the specified output signals into the timing graph.
    fn init_required_output_signals(&mut self) -> Result<(), StaError> {
        log::debug!("init required output signals");
        for ((pin, edge_polarity), required_signal) in &self.required_output_signals {
            let terminal = db::TerminalId::PinId(pin.clone());
            self.timing_graph
                .add_terminal_to_frontier(&terminal, Some(*edge_polarity));

            // Ignore pins which are not part of the netlist.
            if let Some(&[node_rise, node_fall]) = self.timing_graph.term2node.get(&terminal) {
                let node = match edge_polarity {
                    RiseFall::Rise => node_rise,
                    RiseFall::Fall => node_fall,
                };

                let terminal_ref = self.netlist().terminal_ref(&terminal);
                log::debug!(
                    "Set required output signal for {}: {:?}",
                    terminal_ref.qname(PATH_SEPARATOR),
                    required_signal
                );

                let mut node_data = self
                    .timing_graph
                    .get_node_data_mut(node)
                    .expect("failed to get node data");

                node_data.required_signal = Some(required_signal.clone());
            }
        }
        Ok(())
    }

    /// Copy the specified output loads into the timing graph.
    fn init_output_loads(&mut self) -> Result<(), StaError> {
        log::debug!("init output loads");
        for (pin, load) in &self.output_loads {
            let terminal = db::TerminalId::PinId(pin.clone());

            // Mark rise and fall node to be updated.
            self.timing_graph.add_terminal_to_frontier(&terminal, None);

            // Ignore pins which are not part of the netlist.
            if let Some(&nodes) = self.timing_graph.term2node.get(&terminal) {
                let terminal_ref = self.netlist().terminal_ref(&terminal);
                log::debug!(
                    "Set output load for {}: {:?}",
                    terminal_ref.qname(PATH_SEPARATOR),
                    load
                );

                todo!();
            }
        }
        Ok(())
    }

    fn init_clock_signals(&mut self) -> Result<(), StaError> {
        log::debug!("Initialize clock signals");
        log::debug!("Number of defined clocks: {}", self.clocks.len());
        for (clock_terminal, clock_def) in &self.clocks {
            assert!(
                clock_def.clock_id.is_some(),
                "clock_id is not set for the clock definition"
            );

            let terminal_ref = self.netlist.terminal_ref(clock_terminal);

            log::debug!("Set clock for {}", terminal_ref.qname(PATH_SEPARATOR));

            // Get graph nodes which represent the rising and falling edge of the clock input.
            let nodes = self
                .timing_graph
                .term2node
                .get(clock_terminal)
                .ok_or_else(|| {
                    StaError::Other(format!(
                        "Cannot find clock in timing graph: {}",
                        terminal_ref.qname(PATH_SEPARATOR)
                    ))
                })?;

            let signals = [&clock_def.rising_edge, &clock_def.falling_edge];

            // Mark clock nodes in the timing graph.
            for (node, signal) in nodes.iter().zip(signals) {
                // Get node data of the node which represents the clock terminal.
                let mut node_data = self
                    .timing_graph
                    .get_node_data_mut(*node)
                    .expect("graph node has no data");

                node_data.signal =
                    Some(SignalWithClock::new(signal.clone()).with_clock_id(clock_def.clock_id));

                node_data.is_primary_input = true;
            }

            // Mark change for the next update.
            self.timing_graph
                .add_terminal_to_frontier(clock_terminal, None);
        }
        Ok(())
    }

    /// Compute actual and required arival times.
    fn propagate_signals(
        &mut self,
        net_loads: &FnvHashMap<N::NetId, Lib::Load>,
    ) -> Result<(), StaError>
    where
        Lib: Sync,
        N: db::NetlistBaseMT,
    {
        log::debug!("compute actual arrival times");

        self.generation += 1;

        // Take and reset the frontier.
        // For the first propagation, the frontier should consist only of the root node.
        let frontier = self.timing_graph.take_frontier();

        let zero_delay_ic_model = ZeroInterconnectDelayModel::new(&self.cell_model.inner);
        let clock_aware_ic_model = ClockAwareInterconnectModel::new(zero_delay_ic_model);

        log::debug!("propagate signals");

        propagate_signals_incremental(
            self.netlist(),
            &self.timing_graph,
            &self.cell_model,
            &clock_aware_ic_model,
            &PrecomputedOutputLoads { loads: net_loads },
            frontier.iter().copied(),
            self.generation,
        );

        Ok(())
    }

    /// Get a list all graph nodes sorted topologically.
    /// Used for debug printing only.
    fn toposort_delay_graph(&self) -> Result<Vec<TerminalId<N>>, StaError> {
        // Create the delay arc graph by filtering the graph edges (remove constraint arcs).
        let delay_graph =
            petgraph::visit::EdgeFiltered::from_fn(&self.timing_graph.arc_graph, |edge_ref| {
                edge_ref.weight().edge_type.is_delay_arc()
            });

        // Create the constraint arc graph by filtering the graph edges (remove delay arcs).
        let _constraint_graph =
            petgraph::visit::EdgeFiltered::from_fn(&self.timing_graph.arc_graph, |edge_ref| {
                edge_ref.weight().edge_type.is_constraint_arc()
            });

        // TODO: (optimization) To enable parallel computation the graph should be topo-sorted with levels.
        // Nodes have no connections to other nodes on the same level and hence for each level
        // the values (slew, ...) can be computed for all nodes in parallel.
        log::debug!("Sort graph nodes topologically.");
        let topo_sorted: Vec<TerminalId<_>> = {
            let topo = petgraph::algo::toposort(&delay_graph, None);
            match topo {
                Ok(sorted) => sorted
                    .iter()
                    .filter(|&&id| {
                        id != self.timing_graph.aat_source_node
                            && id != self.timing_graph.rat_source_node
                    })
                    .map(|id| self.timing_graph.node2term[id].clone())
                    .collect(),
                Err(cycle) => {
                    log::warn!("netlist has combinational cycle");
                    if let Some(cycle_node) = self.timing_graph.node2term.get(&cycle.node_id()) {
                        let term_id = self.netlist().terminal_ref(cycle_node);
                        log::warn!(
                            "combinational cycle through node: {}",
                            term_id.qname(PATH_SEPARATOR)
                        );
                    }
                    return Err(StaError::CombinationalCycle);
                }
            }
        };

        Ok(topo_sorted)
    }

    fn debug_print_actual_signals(&self) {
        // Print actual signals.
        for (_n, weight) in self.timing_graph.arc_graph.node_references() {
            println!(
                "{:?}: {:?}",
                weight.node_type,
                weight.borrow_data_cell().try_read().unwrap().signal
            );
        }
    }

    fn debug_print_timing_graph(&self) {
        // println!("Topological order of graph nodes:");

        // let topo_sorted = self.toposort_delay_graph().unwrap();

        // for term in &topo_sorted {
        //     println!(
        //         "  - {}",
        //         self.netlist().terminal_ref(term).qname(PATH_SEPARATOR)
        //     );
        // }

        let dot = graphviz::TimingGraphDot::new(&self.timing_graph, self.netlist());

        let dot_format = format!("{:?}", dot);
        println!("{}", dot_format);
    }

    /// Do static timing analysis of the `top` cell.
    /// A single clock is allowed and specified with `clock_input`.
    /// Results are just printed on stdout.
    fn run_sta(&mut self) -> Result<(), StaError>
    where
        Lib: Sync,
        N: db::NetlistBaseMT,
    {
        // Do sanity check on the timing library.
        // TODO: don't do this for incremental updates or only if new types of cells have been added.
        if self.need_check_library {
            self.check_library()?;
            self.need_check_library = false;
        }

        self.check_clock_sources()?;

        self.init_input_signals()?;
        self.init_output_loads()?;
        self.init_required_output_signals()?;

        self.init_clock_signals()?;

        // Compute all output load capacitances.
        // TODO: compute incrementally
        // TODO: add user defined output loads
        let net_loads = compute_net_loads(&self.top_cell_ref(), &self.cell_model.inner);

        #[cfg(debug_assertions)]
        self.timing_graph.check_cycles()?;

        self.propagate_signals(&net_loads)?;
        //self.debug_print_actual_signals();
        self.debug_print_timing_graph();

        Ok(())
    }

    /// Check that all cells in the circuit are covered by the library.
    /// TODO: Maybe move this into the library adapter.
    fn check_library(&self) -> Result<(), StaError> {
        log::debug!("check timing library");

        let top = self.top_cell_ref();
        let netlist = self.netlist();

        let mut missing_cells: FnvHashSet<N::CellId> = Default::default();

        for leaf_cell in top.each_cell_dependency() {
            // TODO: Check if cell is contained in the library.
        }

        if !missing_cells.is_empty() {
            let cell_names: Vec<String> = missing_cells
                .iter()
                .map(|c| netlist.cell_name(c).into())
                .collect();
            log::error!(
                "Cells not found in liberty library: {}",
                cell_names.join(", ")
            );
            Err(StaError::MissingCellsInLiberty(cell_names))
        } else {
            Ok(())
        }
    }

    /// Do some sanity checks.
    fn check_clock_sources(&self) -> Result<(), StaError> {
        log::debug!("validate clock sources");

        for clock in self.clocks.keys() {
            let clock_input = self.netlist().terminal_ref(clock);
            if self.top_cell != clock_input.parent().id() {
                log::error!(
                    "clock source '{}' does not live in top cell '{}' but in '{}",
                    clock_input.qname(PATH_SEPARATOR),
                    self.top_cell_ref().name(),
                    clock_input.parent().name()
                );

                return Err(StaError::Other(
                    "clock source does not live in top cell".into(),
                ));
            }
        }

        Ok(())
    }
}

/// Simple implementation of a net load model.
/// The net loads are precomputed and stored in a hash map.
struct PrecomputedOutputLoads<'a, Net, Load> {
    loads: &'a FnvHashMap<Net, Load>,
}

impl<'a, Net, Load> LoadBase for PrecomputedOutputLoads<'a, Net, Load>
where
    Load: Zero + Clone + Debug + Send + Sync,
{
    type Load = Load;

    fn sum_loads(&self, load1: &Self::Load, load2: &Self::Load) -> Self::Load {
        todo!()
    }
}

impl<'a, N, Load> InterconnectLoadModel<N> for PrecomputedOutputLoads<'a, N::NetId, Load>
where
    Load: Zero + Clone + Debug + Send + Sync,
    N: db::NetlistBase,
{
    fn interconnect_load(&self, netlist: &N, driver_terminal: &TerminalId<N>) -> Self::Load {
        let net = netlist.net_of_terminal(driver_terminal);
        net.and_then(|net| self.loads.get(&net))
            .cloned()
            .unwrap_or(Self::Load::zero())
    }
}

impl<'a, N, Lib> TimingQuery for Timed<'a, N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
    type NetlistIds = N;

    type ArrivalTime = Lib::Signal;

    type RequiredArrivalTime = Lib::RequiredSignal;

    type Slack = Lib::Slack;

    fn report_aat(
        &self,
        pin: db::TerminalId<N>,
        edge_polarity: RiseFall,
    ) -> Option<Self::ArrivalTime> {
        self.timing_graph
            .get_terminal_data(&pin, edge_polarity)
            .and_then(|d| d.signal.as_ref().map(|s| s.inner().clone()))
    }

    fn report_rat(
        &self,
        pin: db::TerminalId<N>,
        edge_polarity: RiseFall,
    ) -> Option<Self::RequiredArrivalTime> {
        self.timing_graph
            .get_terminal_data(&pin, edge_polarity)
            .and_then(|d| d.required_signal.as_ref().map(|s| s.inner().clone()))
    }

    fn report_slack(&self, pin: db::TerminalId<N>, edge_polarity: RiseFall) -> Option<Self::Slack> {
        self.timing_graph
            .get_terminal_data(&pin, edge_polarity)
            .and_then(|d| {
                let aat = d.signal.as_ref()?;
                let rat = d.required_signal.as_ref()?;

                self.cell_model.get_slack(aat, rat).into()
            })
    }

    fn report_timing(&self) -> Vec<()> {
        todo!()
    }
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N))]
impl<'a, N, Lib> db::HierarchyIds for Timed<'a, N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N))]
impl<'a, N, Lib> db::NetlistIds for Timed<'a, N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N))]
impl<'a, N, Lib> db::LayoutIds for Timed<'a, N, Lib>
where
    N: LayoutIds + NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<'b, N, Lib> db::HierarchyBase for Timed<'b, N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
    type NameType = N::NameType;
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<'b, N, Lib> db::NetlistBase for Timed<'b, N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<'b, N, Lib> db::LayoutBase for Timed<'b, N, Lib>
where
    N: NetlistBase + LayoutBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<'b, N, Lib> db::L2NBase for Timed<'b, N, Lib>
where
    N: L2NBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N))]
impl<N, Lib> db::HierarchyIds for SimpleSTA<N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N))]
impl<N, Lib> db::NetlistIds for SimpleSTA<N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N))]
impl<N, Lib> db::LayoutIds for SimpleSTA<N, Lib>
where
    N: LayoutIds + NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<N, Lib> db::HierarchyBase for SimpleSTA<N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
    type NameType = N::NameType;
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<N, Lib> db::NetlistBase for SimpleSTA<N, Lib>
where
    N: NetlistBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<N, Lib> db::LayoutBase for SimpleSTA<N, Lib>
where
    N: NetlistBase + LayoutBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<N, Lib> db::L2NBase for SimpleSTA<N, Lib>
where
    N: L2NBase,
    Lib: DelayBase + ConstraintBase,
{
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<N, Lib> db::HierarchyEdit for SimpleSTA<N, Lib>
where
    N: NetlistBase + HierarchyEdit,
    Lib: DelayBase + ConstraintBase + CellDelayModel<N> + CellConstraintModel<N>,
{
    fn create_cell(&mut self, name: Self::NameType) -> Self::CellId {
        self.netlist.create_cell(name)
    }

    fn remove_cell(&mut self, cell_id: &Self::CellId) {
        assert!(
            cell_id != &self.top_cell,
            "cannot remove the cell which is currently selected for static timing analysis"
        );

        // Remove all instances of this cell from the timing graph.
        let cell = self.netlist.cell_ref(cell_id);
        for cell_inst in cell.each_reference() {
            self.timing_graph.remove_cell_instance(&cell_inst);
        }

        self.netlist.remove_cell(cell_id)
    }

    fn create_cell_instance(
        &mut self,
        parent_cell: &Self::CellId,
        template_cell: &Self::CellId,
        name: Option<Self::NameType>,
    ) -> Self::CellInstId {
        // This potentially adds a new type of cell to the circuit.
        // TODO: Most often this does *not* introduce a new cell type. Now this leads unnecessary checks.
        self.need_check_library = true;

        let inst = self
            .netlist
            .create_cell_instance(parent_cell, template_cell, name);

        if parent_cell == &self.top_cell {
            self.timing_graph.create_cell_instance(
                &self.netlist.cell_instance_ref(&inst),
                &self.cell_model.inner,
                &self.cell_model.inner,
            )
        }

        inst
    }

    fn remove_cell_instance(&mut self, inst: &Self::CellInstId) {
        if self.top_cell == self.netlist.parent_cell(inst) {
            todo!("remove graph nodes")
        }

        self.netlist.remove_cell_instance(inst)
    }
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<N, Lib> db::NetlistEdit for SimpleSTA<N, Lib>
where
    N: NetlistEdit,
    Lib: DelayBase + ConstraintBase + CellDelayModel<N> + CellConstraintModel<N>,
{
    fn create_pin(
        &mut self,
        cell: &Self::CellId,
        name: Self::NameType,
        direction: Direction,
    ) -> Self::PinId {
        let pin_id = self.netlist.create_pin(cell, name, direction);

        if cell == &self.top_cell {
            self.timing_graph
                .create_terminal(db::TerminalId::PinId(pin_id.clone()));
        } else {
            // Adding a pin to a cell might bring this circuit out of sync with the library.
            self.need_check_library = true;
            // Add the pin on all existing instances of `cell`.
            for cell_inst in self.netlist.each_cell_reference(cell) {
                let pin_inst = self.netlist.pin_instance(&cell_inst, &pin_id);
                self.timing_graph
                    .create_terminal(db::TerminalId::PinInstId(pin_inst));
            }
        }

        pin_id
    }

    fn remove_pin(&mut self, id: &Self::PinId) {
        if self.netlist.parent_cell_of_pin(id) == self.top_cell {
            self.timing_graph.remove_pin(id.clone());
        } else {
            // Remobing a pin might bring this circuit out of sync with the library.
            self.need_check_library = true;
            // Remove the pin from all cell instances.
            let pin_ref = self.netlist.pin_ref(id);
            let cell = pin_ref.cell();
            for inst in cell.each_reference() {
                self.timing_graph
                    .remove_pin_instance(inst.pin_instance(id).id());
            }
        }
        self.netlist.remove_pin(id)
    }

    fn remove_net(&mut self, net: &Self::NetId) {
        if self.netlist.parent_cell_of_net(net) == self.top_cell {
            let result = self.timing_graph.remove_net(&self.netlist.net_ref(net));
            if let Err(e) = result {
                panic!("failed to remove net: {}", e);
            }
        }
        self.netlist.remove_net(net)
    }

    fn connect_pin(&mut self, pin: &Self::PinId, net: Option<Self::NetId>) -> Option<Self::NetId> {
        let pin_ref = self.netlist.pin_ref(pin);
        if pin_ref.cell().id() == self.top_cell {
            self.timing_graph
                .connect_terminal(pin_ref.into_terminal(), net.clone());
        }
        self.netlist.connect_pin(pin, net)
    }

    fn connect_pin_instance(
        &mut self,
        pin: &Self::PinInstId,
        net: Option<Self::NetId>,
    ) -> Option<Self::NetId> {
        let old_net = self.netlist.connect_pin_instance(pin, net.clone());

        let pin_inst_ref = self.netlist.pin_instance_ref(pin);
        if pin_inst_ref.cell_instance().parent().id() == self.top_cell {
            self.timing_graph
                .connect_terminal(pin_inst_ref.into_terminal(), net);
        }

        old_net
    }
}

#[libreda_db::derive::fill(libreda_db::derive::delegate(N; self.netlist))]
impl<N, Lib> db::LayoutEdit for SimpleSTA<N, Lib>
where
    N: NetlistBase + LayoutEdit,
    Lib: DelayBase + ConstraintBase + CellDelayModel<N> + CellConstraintModel<N>,
{
    fn insert_shape(
        &mut self,
        _parent_cell: &Self::CellId,
        _layer: &Self::LayerId,
        _geometry: db::Geometry<Self::Coord>,
    ) -> Self::ShapeId {
        todo!("editing the layout of a timed circuit is not supported yet")
    }

    fn remove_shape(&mut self, shape_id: &Self::ShapeId) -> Option<db::Geometry<Self::Coord>> {
        todo!("editing the layout of a timed circuit is not supported yet")
    }

    fn replace_shape(
        &mut self,
        _shape_id: &Self::ShapeId,
        _geometry: db::Geometry<Self::Coord>,
    ) -> db::Geometry<Self::Coord> {
        todo!("editing the layout of a timed circuit is not supported yet")
    }

    fn set_transform(
        &mut self,
        _cell_inst: &Self::CellInstId,
        _tf: db::SimpleTransform<Self::Coord>,
    ) {
        todo!("editing the layout of a timed circuit is not supported yet")
    }
}

impl<N, Lib> db::L2NEdit for SimpleSTA<N, Lib>
where
    N: L2NEdit,
    Lib: DelayBase + ConstraintBase + CellDelayModel<N> + CellConstraintModel<N>,
{
    fn set_pin_of_shape(
        &mut self,
        shape_id: &Self::ShapeId,
        pin: Option<Self::PinId>,
    ) -> Option<Self::PinId> {
        let update_top_cell = self.netlist.parent_of_shape(shape_id).0 == self.top_cell;

        if update_top_cell {
            // Mark the change for incremental updates.
            if let Some(p) = pin.clone() {
                self.timing_graph
                    .add_terminal_to_frontier(&db::TerminalId::PinId(p), None);
            }
        }

        // Update underlying netlist.
        let old_pin = self.netlist.set_pin_of_shape(shape_id, pin);

        if update_top_cell {
            // Mark the change for incremental updates.
            if let Some(p) = old_pin.clone() {
                self.timing_graph
                    .add_terminal_to_frontier(&db::TerminalId::PinId(p), None);
            }
        }

        old_pin
    }

    fn set_net_of_shape(
        &mut self,
        shape_id: &Self::ShapeId,
        net: Option<Self::NetId>,
    ) -> Option<Self::NetId> {
        let update_top_cell = self.netlist.parent_of_shape(shape_id).0 == self.top_cell;

        if update_top_cell {
            // Mark the change for incremental updates.
            if let Some(n) = &net {
                for t in self.netlist.each_terminal_of_net(n) {
                    self.timing_graph.add_terminal_to_frontier(&t.cast(), None);
                }
            }
        }

        // Update underlying netlist.
        let old_net = self.netlist.set_net_of_shape(shape_id, net);

        if update_top_cell {
            // Mark the change for incremental updates.
            if let Some(n) = &old_net {
                for t in self.netlist.each_terminal_of_net(n) {
                    self.timing_graph.add_terminal_to_frontier(&t.cast(), None);
                }
            }
        }

        old_net
    }
}

#[test]
fn test_uom() {
    // Experiment with uom.
    use uom::si::capacitance::femtofarad;
    use uom::si::electric_current::femtoampere;
    use uom::si::f64::*;

    let i = ElectricCurrent::new::<femtoampere>(1.0);
    let c = Capacitance::new::<femtofarad>(2.0);
    let _time = c / i;
}

#[test]
fn test_uom_unit_elimination() {
    use uom::si::capacitance::femtofarad;
    use uom::si::electric_current::femtoampere;
    use uom::si::f64::*;

    let i = ElectricCurrent::new::<femtoampere>(1.0);
    let c = Capacitance::new::<femtofarad>(2.0);

    let ratio1 = i / i; // Division should strip the units.
    let ratio2 = c / c;

    let _unitless_sum = ratio1 + ratio2;
}