sv_sim_sim/constraints/

order.rs

//! Variable solve order from `solve ... before` (plan C4; LRM 18.5.9).
//!
//! `solve a before b;` says `a` is solved first, uniformly over the values it
//! can take in *some* legal solution, and then `b` is solved given `a`. A
//! constraint block can hold any number of these, so they form a directed
//! graph over the random variables and the LRM asks for three things of it:
//!
//! * it must be acyclic ("circular dependencies ... are not allowed");
//! * variables that are not ordered at all are solved *with the last set* of
//!   ordered variables (so an unconstrained-by-ordering variable behaves like
//!   the last ordered one: Table 18-1 is simply the case where nothing is
//!   ordered and everything is one set);
//! * a variable that is only partially ordered is solved "with the latest set
//!   of variables that meets the constraints" (as late as the edges allow).
//!
//! [`levels`] gives each variable its *level*: level 0 is solved first and the
//! highest level is solved last. A variable's level is `L - h` where `h` is the
//! length of the longest chain of `before` edges leaving it and `L` is the
//! longest chain anywhere, which is exactly the as-late-as-possible schedule
//! of the three rules above (a variable no edge leaves, ordered or not, has
//! `h = 0` and lands in the last level). [`groups`] collects the variables of
//! each level, in id order, in the shape
//! [`super::solve::Solver::sample_groups`] consumes.
//!
//! `randc` variables are *not* part of this graph: they are always solved
//! before every `rand` variable (LRM 18.4.2) and cannot appear in a `solve`
//! (LRM 18.5.9); the builder rejects the latter and the solve runs them first.

use super::ir::VarId;
use core::fmt;

/// Why a set of `before` edges has no solve order.
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum OrderError {
    /// The edges contain a cycle (LRM 18.5.9: "circular dependencies ... are
    /// not allowed"). `vars` is one cycle, in `before` order, without
    /// repeating its first variable (a self-edge `solve a before a` is the
    /// one-variable cycle).
    Cycle {
        /// The variables on the cycle.
        vars: Vec<VarId>,
    },
    /// An edge names a variable id outside `0..n`.
    UnknownVar {
        /// The offending id.
        var: VarId,
    },
}

impl fmt::Display for OrderError {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            OrderError::Cycle { vars } => write!(
                f,
                "the `solve ... before` constraints are circular through random variables {vars:?} \
                 (IEEE 1800-2023 18.5.9)"
            ),
            OrderError::UnknownVar { var } => write!(
                f,
                "a `solve ... before` edge names random variable #{var} which does not exist"
            ),
        }
    }
}

impl std::error::Error for OrderError {}

/// The level of each of the `n` variables under the `before` edges
/// `(first, later)` (module docs): 0 is solved first, `max` last. With no
/// edges every variable is at level 0, one set.
pub fn levels(n: usize, edges: &[(VarId, VarId)]) -> Result<Vec<usize>, OrderError> {
    let mut succ: Vec<Vec<usize>> = vec![Vec::new(); n];
    for &(a, b) in edges {
        for v in [a, b] {
            if v as usize >= n {
                return Err(OrderError::UnknownVar { var: v });
            }
        }
        if !succ[a as usize].contains(&(b as usize)) {
            succ[a as usize].push(b as usize);
        }
    }
    // Peel from the sinks: a variable is finished once all its successors
    // are, and its height is one more than its tallest successor's.
    let mut pred: Vec<Vec<usize>> = vec![Vec::new(); n];
    for (a, ss) in succ.iter().enumerate() {
        for &b in ss {
            pred[b].push(a);
        }
    }
    let mut pending: Vec<usize> = succ.iter().map(Vec::len).collect();
    let mut height = vec![0usize; n];
    let mut ready: Vec<usize> = (0..n).filter(|&v| pending[v] == 0).collect();
    let mut done = 0usize;
    while let Some(v) = ready.pop() {
        done += 1;
        for &p in &pred[v] {
            height[p] = height[p].max(height[v] + 1);
            pending[p] -= 1;
            if pending[p] == 0 {
                ready.push(p);
            }
        }
    }
    if done < n {
        // Every unfinished variable still has an unfinished successor, so
        // walking successors among them must revisit one: that is a cycle.
        let unfinished: Vec<bool> = pending.iter().map(|&p| p > 0).collect();
        let start = (0..n).find(|&v| unfinished[v]).expect("done < n");
        let mut seen_at = vec![usize::MAX; n];
        let mut path: Vec<usize> = Vec::new();
        let mut cur = start;
        loop {
            if seen_at[cur] != usize::MAX {
                let vars = path[seen_at[cur]..].iter().map(|&v| v as VarId).collect();
                return Err(OrderError::Cycle { vars });
            }
            seen_at[cur] = path.len();
            path.push(cur);
            cur = *succ[cur]
                .iter()
                .find(|&&s| unfinished[s])
                .expect("an unfinished variable has an unfinished successor");
        }
    }
    let top = height.iter().copied().max().unwrap_or(0);
    Ok(height.into_iter().map(|h| top - h).collect())
}

/// The variables of each level of [`levels`], first-solved level first, each
/// in id order. Every level is non-empty.
pub fn groups(n: usize, edges: &[(VarId, VarId)]) -> Result<Vec<Vec<VarId>>, OrderError> {
    let lv = levels(n, edges)?;
    let count = lv.iter().copied().max().map_or(0, |m| m + 1);
    let mut out: Vec<Vec<VarId>> = vec![Vec::new(); count];
    for (v, l) in lv.into_iter().enumerate() {
        out[l].push(v as VarId);
    }
    debug_assert!(out.iter().all(|g| !g.is_empty()));
    Ok(out)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn no_edges_is_one_set() {
        assert_eq!(levels(3, &[]).unwrap(), vec![0, 0, 0]);
        assert_eq!(groups(3, &[]).unwrap(), vec![vec![0, 1, 2]]);
        assert_eq!(groups(0, &[]).unwrap(), Vec::<Vec<VarId>>::new());
    }

    #[test]
    fn a_before_b_leaves_unordered_variables_with_the_last_set() {
        // Variables a=0, b=1, u=2 (unordered): u is solved with b, the last
        // ordered set (LRM 18.5.9).
        assert_eq!(levels(3, &[(0, 1)]).unwrap(), vec![0, 1, 1]);
        assert_eq!(groups(3, &[(0, 1)]).unwrap(), vec![vec![0], vec![1, 2]]);
    }

    #[test]
    fn a_partially_ordered_variable_is_solved_as_late_as_the_edges_allow() {
        // a before b before c, and d before c: d has the one edge to the last
        // variable so it is solved with b (level 1), not with a (level 0).
        let e = [(0, 1), (1, 2), (3, 2)];
        assert_eq!(levels(4, &e).unwrap(), vec![0, 1, 2, 1]);
        assert_eq!(groups(4, &e).unwrap(), vec![vec![0], vec![1, 3], vec![2]]);
    }

    #[test]
    fn several_names_on_one_side_fan_in_and_out() {
        // solve a, b before c, d
        let e = [(0, 2), (0, 3), (1, 2), (1, 3)];
        assert_eq!(groups(4, &e).unwrap(), vec![vec![0, 1], vec![2, 3]]);
    }

    #[test]
    fn duplicate_edges_are_harmless() {
        assert_eq!(levels(2, &[(0, 1), (0, 1), (0, 1)]).unwrap(), vec![0, 1]);
    }

    #[test]
    fn cycles_are_rejected_and_named() {
        assert_eq!(
            levels(2, &[(0, 0)]).unwrap_err(),
            OrderError::Cycle { vars: vec![0] }
        );
        let e = levels(3, &[(0, 1), (1, 2), (2, 1)]).unwrap_err();
        let OrderError::Cycle { vars } = e else {
            panic!("{e:?}")
        };
        let mut sorted = vars.clone();
        sorted.sort_unstable();
        assert_eq!(
            sorted,
            vec![1, 2],
            "the cycle, not variable 0 upstream of it"
        );
        // The reported list is a genuine cycle in `before` order.
        assert!(vars == vec![1, 2] || vars == vec![2, 1]);
    }

    #[test]
    fn an_unknown_variable_is_an_error() {
        assert_eq!(
            levels(2, &[(0, 5)]).unwrap_err(),
            OrderError::UnknownVar { var: 5 }
        );
    }

    #[test]
    fn errors_have_messages() {
        assert!(
            OrderError::Cycle { vars: vec![1, 2] }
                .to_string()
                .contains("circular")
        );
        assert!(OrderError::UnknownVar { var: 9 }.to_string().contains("#9"));
    }
}