vj-sim 0.3.0

//! One cross instance: bin tuples, select expressions, sampling and coverage
//! (IEEE 1800-2023 19.6, 19.11.2).
//!
//! A cross is the Cartesian product of the crossed coverpoints' bins. Every
//! point of that space (a *bin tuple*) gets a number by mixed radix, first item
//! most significant, so a select expression is a bit set over the space:
//! `binsof` builds one from per-coverpoint bin masks, `!` complements it, `&&`
//! and `||` intersect and unite, `with` and set expressions filter it. The sets
//! are built once, at construction (the LRM evaluates `with` "at the time the
//! covergroup instance is constructed", 19.6.1.2).

use std::collections::hash_map::Entry;
use std::collections::{BTreeSet, HashMap};

use super::bins::{BinValues, EXPAND_LIMIT, eval_range_list};
use super::coverpoint::{CovEvent, Coverage, Coverpoint, truthy};
use super::decl::{BinKind, CrossDecl, Matches, RangeItem, SelectExpr};
use super::options::{Level, Options, TypeOptions};
use super::value::{CovError, Eval, Expr, Val};

/// A fixed-size set of bin tuples.
#[derive(Clone, Debug, PartialEq)]
struct Bits {
    words: Vec<u64>,
    len: usize,
}

impl Bits {
    fn new(len: usize) -> Bits {
        Bits {
            words: vec![0; len.div_ceil(64)],
            len,
        }
    }

    fn full(len: usize) -> Bits {
        let mut b = Bits::new(len);
        b.words.iter_mut().for_each(|w| *w = !0);
        b.trim();
        b
    }

    /// Clears the unused high bits of the last word.
    fn trim(&mut self) {
        let rem = self.len % 64;
        if rem != 0
            && let Some(last) = self.words.last_mut()
        {
            *last &= (1u64 << rem) - 1;
        }
    }

    fn get(&self, i: usize) -> bool {
        self.words[i / 64] >> (i % 64) & 1 == 1
    }

    fn set(&mut self, i: usize) {
        self.words[i / 64] |= 1 << (i % 64);
    }

    fn not(mut self) -> Bits {
        self.words.iter_mut().for_each(|w| *w = !*w);
        self.trim();
        self
    }

    fn and(&mut self, o: &Bits) {
        self.words
            .iter_mut()
            .zip(&o.words)
            .for_each(|(a, b)| *a &= b);
    }

    fn or(&mut self, o: &Bits) {
        self.words
            .iter_mut()
            .zip(&o.words)
            .for_each(|(a, b)| *a |= b);
    }

    fn subtract(&mut self, o: &Bits) {
        self.words
            .iter_mut()
            .zip(&o.words)
            .for_each(|(a, b)| *a &= !b);
    }

    fn count(&self) -> u64 {
        self.words.iter().map(|w| w.count_ones() as u64).sum()
    }

    fn iter(&self) -> impl Iterator<Item = usize> + '_ {
        (0..self.len).filter(|&i| self.get(i))
    }
}

/// One crossed coverpoint: the bins that take part in the product.
#[derive(Clone, Debug, PartialEq)]
struct Dim {
    coverpoint: String,
    /// Indices into the coverpoint's `bins`, ascending.
    bins: Vec<usize>,
    names: Vec<String>,
    /// Coverpoint bin index to position in `bins`.
    pos_of: HashMap<usize, usize>,
    /// Weight of this dimension in a tuple number.
    stride: usize,
}

impl Dim {
    fn component(&self, tuple: usize) -> usize {
        tuple / self.stride % self.bins.len()
    }
}

/// A user-defined cross bin (`bins`, `ignore_bins`, `illegal_bins`).
#[derive(Clone, Debug, PartialEq)]
pub struct CrossBin {
    pub name: String,
    pub kind: BinKind,
    pub hits: u64,
    /// No bin tuple is left in the bin (everything was ignored or illegal, or
    /// the selection was empty): excluded from coverage (19.11).
    pub empty: bool,
    iff: Option<Expr>,
    members: Bits,
}

impl CrossBin {
    /// How many bin tuples the bin holds.
    pub fn tuple_count(&self) -> u64 {
        self.members.count()
    }
}

#[derive(Debug)]
pub struct Cross {
    pub name: String,
    pub options: Options,
    pub type_options: TypeOptions,
    iff: Option<Expr>,
    ctor: Vec<Val>,
    dims: Vec<Dim>,
    total: usize,
    bins: Vec<CrossBin>,
    /// The bin tuples that keep an automatically generated bin (19.6.1).
    auto: Bits,
    auto_hits: HashMap<usize, u64>,
    /// How many times the cross formed bin tuples.
    pub samples: u64,
}

fn err(cross: &str, detail: impl Into<String>) -> CovError {
    CovError::CrossSelect {
        cross: cross.to_string(),
        detail: detail.into(),
    }
}

/// `binsof(cp.id)` names a bin `id`, or every element `id[...]` of an array.
fn names_bin(name: &str, id: &str) -> bool {
    name == id || name.strip_prefix(id).is_some_and(|r| r.starts_with('['))
}

/// The tuple numbers of the product of `lists` (one position list per
/// dimension), ascending.
fn product_ids(lists: &[Vec<usize>], strides: &[usize]) -> Vec<usize> {
    let mut ids = vec![0usize];
    for (l, &st) in lists.iter().zip(strides) {
        let mut next = Vec::with_capacity(ids.len() * l.len());
        for &base in &ids {
            for &p in l {
                next.push(base + p * st);
            }
        }
        ids = next;
    }
    ids
}

/// Everything select-expression evaluation needs.
struct Sel<'a> {
    cross: &'a str,
    cps: &'a [&'a Coverpoint],
    dims: &'a [Dim],
    total: usize,
    ev: &'a mut dyn Eval,
    ctor: &'a [Val],
    warns: &'a mut Vec<String>,
    cache: HashMap<(usize, usize), BinValues>,
}

impl Sel<'_> {
    fn dim_of(&self, cp: &str) -> Result<usize, CovError> {
        self.dims
            .iter()
            .position(|d| d.coverpoint == cp)
            .ok_or_else(|| {
                err(
                    self.cross,
                    format!("binsof({cp}): not a crossed coverpoint"),
                )
            })
    }

    fn values(&mut self, d: usize, pos: usize) -> Result<BinValues, CovError> {
        if let Some(v) = self.cache.get(&(d, pos)) {
            return Ok(v.clone());
        }
        let cp = self.cps[d];
        let v = cp.bins[self.dims[d].bins[pos]].values(&cp.ty)?;
        self.cache.insert((d, pos), v.clone());
        Ok(v)
    }

    /// The individual values of a bin of an integral dimension.
    fn int_list(&mut self, d: usize, pos: usize, what: &str) -> Result<Vec<i128>, CovError> {
        match self.values(d, pos)? {
            BinValues::Ints(s) => s.values(EXPAND_LIMIT).ok_or(CovError::TooManyValues {
                ctx: format!("cross {}: {what}", self.cross),
                limit: EXPAND_LIMIT,
            }),
            BinValues::Reals(_) => Err(CovError::Unsupported(format!(
                "cross {}: {what} over the real coverpoint {}",
                self.cross, self.dims[d].coverpoint
            ))),
        }
    }

    fn select(&mut self, e: &SelectExpr) -> Result<Bits, CovError> {
        match e {
            SelectExpr::Binsof { cp, bin, intersect } => {
                self.binsof(cp, bin.as_deref(), intersect.as_deref())
            }
            SelectExpr::Not(x) => Ok(self.select(x)?.not()),
            SelectExpr::And(a, b) => {
                let mut x = self.select(a)?;
                x.and(&self.select(b)?);
                Ok(x)
            }
            SelectExpr::Or(a, b) => {
                let mut x = self.select(a)?;
                x.or(&self.select(b)?);
                Ok(x)
            }
            SelectExpr::With { sel, expr, matches } => {
                let s = self.select(sel)?;
                self.with(s, expr, matches)
            }
            SelectExpr::All => Ok(Bits::full(self.total)),
            SelectExpr::Set { expr, matches } => self.set(expr, matches),
        }
    }

    fn binsof(
        &mut self,
        cp: &str,
        bin: Option<&str>,
        intersect: Option<&[RangeItem]>,
    ) -> Result<Bits, CovError> {
        let d = self.dim_of(cp)?;
        let mut chosen: Vec<bool> = vec![true; self.dims[d].bins.len()];
        if let Some(id) = bin {
            if !self.cps[d].bins.iter().any(|b| names_bin(&b.name, id)) {
                return Err(err(
                    self.cross,
                    format!("binsof({cp}.{id}): coverpoint {cp} has no such bin"),
                ));
            }
            for (p, n) in self.dims[d].names.iter().enumerate() {
                chosen[p] = names_bin(n, id);
            }
        }
        if let Some(items) = intersect {
            let ranges = eval_range_list(
                self.cps[d].ty,
                &format!("{}.{} intersect", self.cross, cp),
                items,
                self.ev,
                self.ctor,
                self.warns,
            )?;
            for (p, keep) in chosen.iter_mut().enumerate() {
                if *keep && !self.values(d, p)?.intersects(&ranges)? {
                    *keep = false;
                }
            }
        }
        let mut out = Bits::new(self.total);
        for t in 0..self.total {
            if chosen[self.dims[d].component(t)] {
                out.set(t);
            }
        }
        Ok(out)
    }

    /// `matches n` as a minimum count (`None`: every value tuple).
    fn need(&mut self, m: &Matches) -> Result<Option<u128>, CovError> {
        match m {
            Matches::All => Ok(None),
            Matches::Count(e) => match e.eval(self.ev, self.ctor)? {
                Val::Int(n) if n >= 1 => Ok(Some(n as u128)),
                other => Err(err(
                    self.cross,
                    format!("matches needs a positive integer or $, got {other:?}"),
                )),
            },
        }
    }

    /// The bin tuples of `sel` with enough value tuples satisfying `expr`
    /// (19.6.1.2).
    fn with(&mut self, sel: Bits, expr: &Expr, m: &Matches) -> Result<Bits, CovError> {
        let need = self.need(m)?;
        let n = self.dims.len();
        let mut lists: HashMap<(usize, usize), Vec<i128>> = HashMap::new();
        let mut out = Bits::new(self.total);
        let mut evals: u128 = 0;
        for t in sel.iter() {
            let mut vals: Vec<Vec<i128>> = Vec::with_capacity(n);
            for d in 0..n {
                let pos = self.dims[d].component(t);
                if let Entry::Vacant(e) = lists.entry((d, pos)) {
                    e.insert(self.int_list(d, pos, "a with clause")?);
                }
                vals.push(lists[&(d, pos)].clone());
            }
            if vals.iter().any(|v| v.is_empty()) {
                continue;
            }
            let mut idx = vec![0usize; n];
            let mut sat: u128 = 0;
            let mut selected = need.is_none();
            'tuples: loop {
                evals += 1;
                if evals > EXPAND_LIMIT {
                    return Err(CovError::TooManyValues {
                        ctx: format!("cross {} with clause", self.cross),
                        limit: EXPAND_LIMIT,
                    });
                }
                let mut args = self.ctor.to_vec();
                args.extend((0..n).map(|d| Val::Int(vals[d][idx[d]])));
                let ok = truthy(expr.eval(self.ev, &args)?, "cross with clause")?;
                match need {
                    Some(k) if ok => {
                        sat += 1;
                        if sat >= k {
                            selected = true;
                            break 'tuples;
                        }
                    }
                    Some(_) => {}
                    None if !ok => {
                        selected = false;
                        break 'tuples;
                    }
                    None => {}
                }
                // odometer, last dimension fastest
                let mut d = n;
                loop {
                    if d == 0 {
                        break 'tuples;
                    }
                    d -= 1;
                    idx[d] += 1;
                    if idx[d] < vals[d].len() {
                        break;
                    }
                    idx[d] = 0;
                }
            }
            if selected {
                out.set(t);
            }
        }
        Ok(out)
    }

    /// A cross set expression: the bin tuples that hold enough of the listed
    /// value tuples (19.6.1.4).
    fn set(&mut self, expr: &Expr, m: &Matches) -> Result<Bits, CovError> {
        let need = self.need(m)?;
        let n = self.dims.len();
        let v = expr.eval(self.ev, self.ctor)?;
        let Val::List(elems) = v else {
            return Err(err(
                self.cross,
                format!("a set expression must be a queue of tuples, got {v:?}"),
            ));
        };
        let mut tuples: BTreeSet<Vec<i128>> = BTreeSet::new();
        'elems: for e in elems {
            let Val::List(vs) = e else {
                return Err(err(
                    self.cross,
                    format!("a set expression element must be a tuple, got {e:?}"),
                ));
            };
            if vs.len() != n {
                return Err(err(
                    self.cross,
                    format!("a tuple has {} values, the cross has {n} items", vs.len()),
                ));
            }
            let mut t = Vec::with_capacity(n);
            for v in vs {
                match v {
                    Val::Int(i) => t.push(i),
                    // an x/z value is in no bin
                    Val::Unknown | Val::Pat { .. } => continue 'elems,
                    other => {
                        return Err(CovError::BadValue {
                            ctx: format!("cross {} set tuple", self.cross),
                            got: format!("{other:?}"),
                        });
                    }
                }
            }
            tuples.insert(t);
        }
        let strides: Vec<usize> = self.dims.iter().map(|d| d.stride).collect();
        let mut counts: HashMap<usize, u128> = HashMap::new();
        for t in &tuples {
            let mut lists: Vec<Vec<usize>> = Vec::with_capacity(n);
            for (d, &value) in t.iter().enumerate() {
                let mut ps = Vec::new();
                for p in 0..self.dims[d].bins.len() {
                    match self.values(d, p)? {
                        BinValues::Ints(s) if s.contains(value) => ps.push(p),
                        BinValues::Ints(_) => {}
                        BinValues::Reals(_) => {
                            return Err(CovError::Unsupported(format!(
                                "cross {}: a set expression over the real coverpoint {}",
                                self.cross, self.dims[d].coverpoint
                            )));
                        }
                    }
                }
                lists.push(ps);
            }
            for id in product_ids(&lists, &strides) {
                *counts.entry(id).or_insert(0) += 1;
            }
        }
        let mut out = Bits::new(self.total);
        for (id, c) in counts {
            let take = match need {
                Some(k) => c >= k,
                None => {
                    let mut all: u128 = 1;
                    for d in 0..n {
                        let BinValues::Ints(s) = self.values(d, self.dims[d].component(id))? else {
                            unreachable!("real dimensions were rejected above");
                        };
                        all = all.saturating_mul(s.count());
                    }
                    c >= all
                }
            };
            if take {
                out.set(id);
            }
        }
        Ok(out)
    }
}

impl Cross {
    /// Instantiates `decl` over the already-built coverpoints `cps` (in item
    /// order) of a covergroup with options `cg_opts` / `cg_topts`.
    pub fn new(
        decl: &CrossDecl,
        cps: &[&Coverpoint],
        cg_opts: &Options,
        cg_topts: &TypeOptions,
        ev: &mut dyn Eval,
        ctor: &[Val],
    ) -> Result<(Cross, Vec<String>), CovError> {
        let name = decl.name.as_str();
        if decl.items.len() < 2 {
            return Err(err(name, "a cross needs at least two items (Syntax 19-4)"));
        }
        if cps.len() != decl.items.len() || cps.iter().zip(&decl.items).any(|(c, n)| &c.name != n) {
            return Err(err(
                name,
                "the coverpoints given do not match the cross items",
            ));
        }
        let mut options = cg_opts.inherit();
        for (n, e) in &decl.options {
            let v = e.eval(ev, ctor)?;
            options.set(Level::Cross, n, &v)?;
        }
        let mut type_options = cg_topts.inherit();
        for (n, e) in &decl.type_options {
            let v = e.eval(ev, ctor)?;
            type_options.set(Level::Cross, n, &v)?;
        }

        let mut dims: Vec<Dim> = Vec::with_capacity(cps.len());
        for cp in cps {
            let bins = cp.cross_bins();
            let names = bins.iter().map(|&i| cp.bins[i].name.clone()).collect();
            let pos_of = bins.iter().enumerate().map(|(p, &i)| (i, p)).collect();
            dims.push(Dim {
                coverpoint: cp.name.clone(),
                bins,
                names,
                pos_of,
                stride: 1,
            });
        }
        let mut total: u128 = 1;
        for d in dims.iter_mut().rev() {
            d.stride = total.min(usize::MAX as u128) as usize;
            total = total.saturating_mul(d.bins.len() as u128);
            if total > EXPAND_LIMIT {
                return Err(CovError::TooManyValues {
                    ctx: format!("cross {name}"),
                    limit: EXPAND_LIMIT,
                });
            }
        }
        let total = total as usize;

        let mut warns = Vec::new();
        let mut sel = Sel {
            cross: name,
            cps,
            dims: &dims,
            total,
            ev,
            ctor,
            warns: &mut warns,
            cache: HashMap::new(),
        };
        let mut bins: Vec<CrossBin> = Vec::with_capacity(decl.bins.len());
        for b in &decl.bins {
            let members = sel.select(&b.select)?;
            bins.push(CrossBin {
                name: b.name.clone(),
                kind: b.kind,
                hits: 0,
                empty: false,
                iff: b.iff.clone(),
                members,
            });
        }

        // 19.6.2, 19.6.3: ignored and illegal products leave every other bin.
        let mut removed = Bits::new(total);
        let mut user_normal = Bits::new(total);
        for b in &bins {
            match b.kind {
                BinKind::Normal => user_normal.or(&b.members),
                BinKind::Ignore | BinKind::Illegal => removed.or(&b.members),
            }
        }
        for b in bins.iter_mut().filter(|b| b.kind == BinKind::Normal) {
            b.members.subtract(&removed);
            b.empty = b.members.count() == 0;
        }
        // 19.6.1: automatic bins stay for the products no user bin took.
        let mut auto = Bits::full(total);
        if options.cross_retain_auto_bins {
            auto.subtract(&user_normal);
            auto.subtract(&removed);
        } else {
            auto = Bits::new(total);
        }

        Ok((
            Cross {
                name: decl.name.clone(),
                options,
                type_options,
                iff: decl.iff.clone(),
                ctor: ctor.to_vec(),
                dims,
                total,
                bins,
                auto,
                auto_hits: HashMap::new(),
                samples: 0,
            },
            warns,
        ))
    }

    /// `<b1,b2,...>`: the name of a bin tuple.
    fn tuple_name(&self, t: usize) -> String {
        let parts: Vec<&str> = self
            .dims
            .iter()
            .map(|d| d.names[d.component(t)].as_str())
            .collect();
        format!("<{}>", parts.join(","))
    }

    fn bin_iff(&self, i: usize, ev: &mut dyn Eval, args: &[Val]) -> Result<bool, CovError> {
        match &self.bins[i].iff {
            None => Ok(true),
            Some(e) => truthy(e.eval(ev, args)?, "cross bin iff"),
        }
    }

    /// Counts one sample. `cps` are the crossed coverpoints (in item order),
    /// already sampled for this event; `sargs` are the `sample()` arguments.
    pub fn sample(
        &mut self,
        cps: &[&Coverpoint],
        ev: &mut dyn Eval,
        sargs: &[Val],
    ) -> Result<Vec<CovEvent>, CovError> {
        if cps.len() != self.dims.len() {
            return Err(err(
                &self.name,
                "sampled with a different number of coverpoints than crossed",
            ));
        }
        // a coverpoint with no usable value (iff false, x/z, ignored, illegal
        // or default) leaves no bin tuple to count (19.6)
        if cps
            .iter()
            .any(|c| !c.last_sampled() || c.last_hits().is_empty())
        {
            return Ok(Vec::new());
        }
        let mut args = self.ctor.clone();
        args.extend_from_slice(sargs);
        if let Some(iff) = &self.iff
            && !truthy(iff.eval(ev, &args)?, "cross iff")?
        {
            return Ok(Vec::new());
        }
        self.samples += 1;
        let lists: Vec<Vec<usize>> = cps
            .iter()
            .zip(&self.dims)
            .map(|(c, d)| {
                c.last_hits()
                    .iter()
                    .filter_map(|b| d.pos_of.get(b).copied())
                    .collect()
            })
            .collect();
        if lists.iter().any(|l| l.is_empty()) {
            return Ok(Vec::new());
        }
        let strides: Vec<usize> = self.dims.iter().map(|d| d.stride).collect();
        let mut events = Vec::new();
        let mut touched: BTreeSet<usize> = BTreeSet::new();
        for t in product_ids(&lists, &strides) {
            // 19.6.3: an illegal product is an error whatever else holds it
            let mut illegal = false;
            for i in 0..self.bins.len() {
                if self.bins[i].kind != BinKind::Illegal || !self.bins[i].members.get(t) {
                    continue;
                }
                illegal = true;
                if self.bin_iff(i, ev, &args)? {
                    self.bins[i].hits = self.bins[i].hits.saturating_add(1);
                    events.push(CovEvent::IllegalBin {
                        coverpoint: self.name.clone(),
                        bin: self.bins[i].name.clone(),
                        value: self.tuple_name(t),
                    });
                }
            }
            if illegal
                || self
                    .bins
                    .iter()
                    .any(|b| b.kind == BinKind::Ignore && b.members.get(t))
            {
                continue;
            }
            for i in 0..self.bins.len() {
                if self.bins[i].kind == BinKind::Normal
                    && self.bins[i].members.get(t)
                    && self.bin_iff(i, ev, &args)?
                {
                    touched.insert(i);
                }
            }
            if self.auto.get(t) {
                let h = self.auto_hits.entry(t).or_insert(0);
                *h = h.saturating_add(1);
            }
        }
        // a cross bin counts once per sample, however many of its products hit
        for i in touched {
            self.bins[i].hits = self.bins[i].hits.saturating_add(1);
        }
        Ok(events)
    }

    /// The user-defined bins, in declaration order.
    pub fn bins(&self) -> &[CrossBin] {
        &self.bins
    }

    /// The names of the bin tuples an explicitly declared bin holds.
    pub fn tuples_of(&self, bin: &str) -> Option<Vec<String>> {
        let b = self.bins.iter().find(|b| b.name == bin)?;
        Some(b.members.iter().map(|t| self.tuple_name(t)).collect())
    }

    /// The automatically generated bins that remain, with their hit counts,
    /// named `<b1,b2,...>`.
    pub fn auto_bins(&self) -> Vec<(String, u64)> {
        self.auto
            .iter()
            .map(|t| {
                (
                    self.tuple_name(t),
                    self.auto_hits.get(&t).copied().unwrap_or(0),
                )
            })
            .collect()
    }

    /// Hit count of the bin called `name` (a user bin, or an automatic
    /// `<b1,b2,...>` one).
    pub fn hits(&self, name: &str) -> Option<u64> {
        if let Some(b) = self.bins.iter().find(|b| b.name == name) {
            return Some(b.hits);
        }
        self.auto
            .iter()
            .find(|&t| self.tuple_name(t) == name)
            .map(|t| self.auto_hits.get(&t).copied().unwrap_or(0))
    }

    /// The cross's coverage: covered / total over the non-empty normal user
    /// bins and the retained automatic bins (19.11.2).
    pub fn coverage(&self) -> Coverage {
        let at_least = self.options.at_least;
        let mut c = Coverage::default();
        for b in &self.bins {
            if b.kind != BinKind::Normal || b.empty {
                continue;
            }
            c.total += 1;
            if b.hits >= at_least {
                c.covered += 1;
            }
        }
        let auto_total = self.auto.count();
        c.total += auto_total;
        c.covered += if at_least == 0 {
            auto_total
        } else {
            self.auto_hits.values().filter(|&&h| h >= at_least).count() as u64
        };
        c
    }

    /// The bins the coverage is measured over, with their hit counts: the
    /// non-empty normal user bins, then the retained automatic bins. What a
    /// merged (type) coverage unions by name (19.11.3).
    pub fn coverage_bins(&self) -> Vec<(String, u64)> {
        let mut out: Vec<(String, u64)> = self
            .bins
            .iter()
            .filter(|b| b.kind == BinKind::Normal && !b.empty)
            .map(|b| (b.name.clone(), b.hits))
            .collect();
        out.extend(self.auto_bins());
        out
    }

    /// The first `cross_num_print_missing` bins not yet covered, the ones a
    /// coverage report lists (Table 19-1).
    pub fn missing_bins(&self) -> Vec<String> {
        self.coverage_bins()
            .into_iter()
            .filter(|(_, h)| *h < self.options.at_least)
            .map(|(n, _)| n)
            .take(usize::try_from(self.options.cross_num_print_missing).unwrap_or(usize::MAX))
            .collect()
    }

    /// Zeroes every bin.
    pub fn reset(&mut self) {
        self.samples = 0;
        self.auto_hits.clear();
        for b in &mut self.bins {
            b.hits = 0;
        }
    }

    /// The number of bin tuples in the cross space.
    pub fn space(&self) -> usize {
        self.total
    }
}