vj-sim 0.2.0

//! Bin construction for one coverpoint instance (IEEE 1800-2023 19.5).
//!
//! Everything that depends on constructor arguments is evaluated here, once,
//! through the [`Eval`] the instance is built with: range ends, tolerances,
//! `number_of_bins`, `with` clauses and set expressions (19.5.1.1, 19.5.1.2).
//! The result is a flat `Vec<Bin>` in declaration order: every element of a
//! `b[]` / `b[N]` array is its own `Bin`, named as 19.5.1 prescribes.

use std::collections::{BTreeMap, HashSet};

use super::decl::{
    ArrayKind, BinBody, BinDecl, BinKind, Bound, CoverpointDecl, RangeItem, RepeatRange, TransRep,
    TransSet,
};
use super::intset::IntSet;
use super::options::{Options, TypeOptions};
use super::trans::{
    self, Alt, MAX_REPEAT, Nfa, Rep, TransElem, TransMatcher, TransSeq, alt_to_seq,
};
use super::value::{CovError, Eval, Expr, TypeInfo, Val};

/// The most individual values/bins one declaration is expanded into. Larger
/// requests are a named [`CovError::TooManyValues`], never a silent truncation.
pub const EXPAND_LIMIT: u128 = 1 << 22;

/// One interval (or single value) of a real coverpoint bin (19.5.1).
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct RealItem {
    pub lo: f64,
    pub hi: f64,
    /// `lo` is always inclusive; `hi` is inclusive for single values, for the
    /// last interval of a range and for ranges not divided into intervals.
    pub hi_closed: bool,
}

impl RealItem {
    pub fn contains(&self, v: f64) -> bool {
        v >= self.lo && (v < self.hi || (self.hi_closed && v == self.hi))
    }

    /// The bin-name text after the opening `[`, including the closing
    /// bracket: `7.5]`, `1.0:2.0)` or `2.0:3.0]` (the interval's own closer
    /// is the name's closer, 19.5.1).
    fn label(&self) -> String {
        if self.lo == self.hi && self.hi_closed {
            format!("{}]", fmt_real(self.lo))
        } else {
            let close = if self.hi_closed { ']' } else { ')' };
            format!(
                "{}:{}{}",
                fmt_real_bound(self.lo),
                fmt_real_bound(self.hi),
                close
            )
        }
    }

    fn overlaps(&self, o: &RealItem) -> bool {
        let a_before_b = self.hi < o.lo || (self.hi == o.lo && !self.hi_closed);
        let b_before_a = o.hi < self.lo || (o.hi == self.lo && !o.hi_closed);
        !(a_before_b || b_before_a)
    }
}

/// `1.0`, `0.75`, `8.4`: shortest text with at least one decimal, with the
/// binary noise of `lo + i*interval` rounded away.
pub fn fmt_real(v: f64) -> String {
    if !v.is_finite() || v.abs() >= 1e15 {
        return format!("{v:?}");
    }
    let s = format!("{v:.12}");
    let s = s.trim_end_matches('0');
    if s.ends_with('.') {
        format!("{s}0")
    } else {
        s.to_string()
    }
}

fn fmt_real_bound(v: f64) -> String {
    if v.is_infinite() {
        "$".to_string()
    } else {
        fmt_real(v)
    }
}

/// What a bin matches at sample time.
#[derive(Clone, Debug, PartialEq)]
pub enum Matcher {
    Ints(IntSet),
    /// Non-array wildcard bin: `(bits, care)` patterns (19.5.4).
    Pats(Vec<(u128, u128)>),
    Reals(Vec<RealItem>),
    /// A default bin: matched by exclusion.
    Default,
    /// A transition bin (19.5.2).
    Trans(TransMatcher),
    /// `default sequence`: transitions no other transition bin takes.
    DefaultSeq,
}

#[derive(Clone, Debug, PartialEq)]
pub struct Bin {
    pub name: String,
    pub kind: BinKind,
    pub matcher: Matcher,
    /// Sample-time `iff` of the bin.
    pub iff: Option<Expr>,
    /// No value can ever land in the bin (empty `[N]` bins, bins whose values
    /// were all ignored/illegal). Empty bins are excluded from coverage (19.5.5).
    pub empty: bool,
    /// `bins x[] = default` / `x[N] = default`: hits are kept per value.
    pub default_array: bool,
    pub hits: u64,
    /// Per-value hit counts of a default array.
    pub default_values: BTreeMap<i128, u64>,
}

impl Bin {
    fn new(name: String, kind: BinKind, matcher: Matcher, iff: Option<Expr>) -> Bin {
        Bin {
            name,
            kind,
            matcher,
            iff,
            empty: false,
            default_array: false,
            hits: 0,
            default_values: BTreeMap::new(),
        }
    }

    /// A value `default` bin.
    pub fn is_default(&self) -> bool {
        matches!(self.matcher, Matcher::Default)
    }

    /// A `default sequence` bin.
    pub fn is_default_seq(&self) -> bool {
        matches!(self.matcher, Matcher::DefaultSeq)
    }

    /// The values the bin holds, as `binsof ... intersect` and cross `with` /
    /// set selection see them: a transition bin contributes the last values of
    /// its sequences (19.6.1.1).
    pub fn values(&self, ty: &TypeInfo) -> Result<BinValues, CovError> {
        match &self.matcher {
            Matcher::Ints(s) => Ok(BinValues::Ints(s.clone())),
            Matcher::Pats(pats) => {
                let mut seq = Vec::new();
                for &(bits, care) in pats {
                    for v in expand_pattern(ty, &self.name, bits, care)? {
                        seq.push((v, v));
                    }
                }
                Ok(BinValues::Ints(IntSet::from_intervals(seq)))
            }
            Matcher::Reals(r) => Ok(BinValues::Reals(r.clone())),
            Matcher::Trans(t) => Ok(BinValues::Ints(t.last.clone())),
            Matcher::Default | Matcher::DefaultSeq => Err(CovError::Unsupported(format!(
                "bin {}: a default bin holds no values to select on",
                self.name
            ))),
        }
    }
}

/// The value content of a bin (see [`Bin::values`]).
#[derive(Clone, Debug, PartialEq)]
pub enum BinValues {
    Ints(IntSet),
    Reals(Vec<RealItem>),
}

impl BinValues {
    /// Whether the bin and the `intersect` ranges share a value.
    pub fn intersects(&self, ranges: &BinValues) -> Result<bool, CovError> {
        match (self, ranges) {
            (BinValues::Ints(a), BinValues::Ints(b)) => Ok(a.intersects(b)),
            (BinValues::Reals(a), BinValues::Reals(b)) => {
                Ok(a.iter().any(|p| b.iter().any(|q| p.overlaps(q))))
            }
            _ => Err(CovError::Unsupported(
                "intersect ranges of a different kind than the bin's values".to_string(),
            )),
        }
    }
}

/// Evaluates a `covergroup_range_list` of type `ty` (an `intersect` list):
/// integral ranges as an [`IntSet`], real ones undivided (19.6.1).
pub fn eval_range_list(
    ty: TypeInfo,
    what: &str,
    items: &[RangeItem],
    ev: &mut dyn Eval,
    ctor: &[Val],
    warns: &mut Vec<String>,
) -> Result<BinValues, CovError> {
    let mut ctx = Ctx {
        cp: what,
        ty,
        ev,
        ctor,
        warns,
    };
    if ty.real {
        // an infinite interval keeps every range one item
        let body = BinBody::Ranges {
            items: items.to_vec(),
            with: None,
        };
        return Ok(BinValues::Reals(real_items(
            &mut ctx,
            what,
            &body,
            f64::INFINITY,
        )?));
    }
    Ok(BinValues::Ints(IntSet::from_intervals(int_items_to_seq(
        &mut ctx, what, items,
    )?)))
}

struct Ctx<'a> {
    cp: &'a str,
    ty: TypeInfo,
    ev: &'a mut dyn Eval,
    ctor: &'a [Val],
    warns: &'a mut Vec<String>,
}

impl Ctx<'_> {
    fn warn(&mut self, bin: &str, msg: String) {
        self.warns
            .push(format!("coverpoint {}: bin {}: {}", self.cp, bin, msg));
    }

    fn eval(&mut self, e: &Expr) -> Result<Val, CovError> {
        e.eval(self.ev, self.ctor)
    }

    /// A `with` clause for candidate `item`: ctor args then `item`.
    fn eval_with(&mut self, e: &Expr, item: i128) -> Result<bool, CovError> {
        let v = match e {
            Expr::Const(v) => v.clone(),
            Expr::Kernel(id) => {
                let mut args = self.ctor.to_vec();
                args.push(Val::Int(item));
                self.ev.eval(*id, &args)?
            }
        };
        match v {
            Val::Int(n) => Ok(n != 0),
            Val::Unknown => Ok(false),
            other => Err(CovError::BadValue {
                ctx: "with clause".to_string(),
                got: format!("{other:?}"),
            }),
        }
    }
}

/// Builds every bin of a coverpoint instance. Returns the bins and the
/// warnings 19.5.7 / 19.7 require.
pub fn build_bins(
    decl: &CoverpointDecl,
    opts: &Options,
    topts: &TypeOptions,
    ev: &mut dyn Eval,
    ctor: &[Val],
) -> Result<(Vec<Bin>, Vec<String>), CovError> {
    let mut warns = Vec::new();
    if !decl.ty.real && decl.ty.width > super::value::MAX_WIDTH {
        return Err(CovError::WidthTooLarge {
            coverpoint: decl.name.clone(),
            width: decl.ty.width,
        });
    }
    let mut ctx = Ctx {
        cp: &decl.name,
        ty: decl.ty,
        ev,
        ctor,
        warns: &mut warns,
    };
    let mut bins: Vec<Bin> = Vec::new();
    let mut defined_normal = false;
    // Transition sequences are evaluated first: ignore/illegal ones also
    // remove sequences from the covered bins (19.5.5, 19.5.6).
    let mut seqs: Vec<Option<Vec<TransSeq>>> = Vec::with_capacity(decl.bins.len());
    let mut removals: Vec<Alt> = Vec::new();
    for b in &decl.bins {
        let BinBody::Trans(sets) = &b.body else {
            seqs.push(None);
            continue;
        };
        if decl.ty.real {
            return Err(CovError::RealUnsupported {
                bin: b.name.clone(),
                what: "a transition bin",
            });
        }
        let compiled = compile_trans_sets(&mut ctx, b, sets)?;
        if b.kind != BinKind::Normal {
            for q in &compiled {
                if !trans::is_bounded(q) {
                    return Err(CovError::TransUnbounded {
                        bin: b.name.clone(),
                        what: "an ignore_bins or illegal_bins transition",
                    });
                }
                removals.extend(trans::expand_alts(&b.name, q)?);
            }
        }
        seqs.push(Some(compiled));
    }
    for (b, sq) in decl.bins.iter().zip(&seqs) {
        if b.kind == BinKind::Normal {
            defined_normal = true;
        }
        match (&b.body, sq) {
            (BinBody::Default, _) => bins.push(build_default(&mut ctx, b)?),
            (BinBody::DefaultSeq, _) => bins.push(build_default_seq(&ctx, b)?),
            (BinBody::Trans(_), Some(s)) => bins.extend(build_trans_bins(b, s, &removals)?),
            (BinBody::Trans(_), None) => {
                unreachable!("every transition bin was compiled by the first pass")
            }
            (body, _) => {
                if decl.ty.real {
                    bins.extend(build_real_bins(&mut ctx, b, body, topts.real_interval)?);
                } else {
                    bins.extend(build_int_bins(&mut ctx, b, body, topts.distribute_first)?);
                }
            }
        }
    }
    if decl.ty.real {
        if !defined_normal {
            return Err(CovError::RealNeedsBins {
                coverpoint: decl.name.clone(),
            });
        }
    } else if !defined_normal {
        bins.extend(build_auto_bins(&ctx, decl, opts));
    }
    mark_empty(&decl.ty, &mut bins);
    if opts.detect_overlap {
        detect_overlap(&decl.name, &bins, &mut warns);
    }
    Ok((bins, warns))
}

fn build_default(ctx: &mut Ctx, b: &BinDecl) -> Result<Bin, CovError> {
    if b.kind == BinKind::Ignore {
        return Err(CovError::Unsupported(format!(
            "bin {}: a default bin cannot be explicitly ignored (19.5.5)",
            b.name
        )));
    }
    if ctx.ty.real && b.array != ArrayKind::None {
        return Err(CovError::RealDefaultArray {
            bin: b.name.clone(),
        });
    }
    let mut bin = Bin::new(b.name.clone(), b.kind, Matcher::Default, b.iff.clone());
    bin.default_array = b.array != ArrayKind::None;
    Ok(bin)
}

// ---------------------------------------------------------------------------
// transition bins (19.5.2)

fn build_default_seq(ctx: &Ctx, b: &BinDecl) -> Result<Bin, CovError> {
    if ctx.ty.real {
        return Err(CovError::RealUnsupported {
            bin: b.name.clone(),
            what: "a default sequence bin",
        });
    }
    if b.kind == BinKind::Ignore {
        return Err(CovError::Unsupported(format!(
            "bin {}: a default sequence cannot be explicitly ignored (19.5.5)",
            b.name
        )));
    }
    if b.array != ArrayKind::None {
        return Err(CovError::Unsupported(format!(
            "bin {}: a default sequence shall not accept multiple bins (19.5.2)",
            b.name
        )));
    }
    Ok(Bin::new(
        b.name.clone(),
        b.kind,
        Matcher::DefaultSeq,
        b.iff.clone(),
    ))
}

/// The values of one `trans_item` (a range list, or a wildcard pattern list).
fn trans_item_values(
    ctx: &mut Ctx,
    bin: &str,
    wildcard: bool,
    items: &[RangeItem],
) -> Result<IntSet, CovError> {
    if !wildcard {
        return Ok(IntSet::from_intervals(int_items_to_seq(ctx, bin, items)?));
    }
    let mut seq = Vec::new();
    for (bits, care) in wild_patterns(ctx, bin, items)? {
        for v in expand_pattern(&ctx.ty, bin, bits, care)? {
            seq.push((v, v));
        }
    }
    Ok(IntSet::from_intervals(seq))
}

/// A `repeat_range` as inclusive `(lo, hi)` counts.
fn repeat_bounds(ctx: &mut Ctx, bin: &str, r: &RepeatRange) -> Result<(u32, u32), CovError> {
    let get = |ctx: &mut Ctx, e: &Expr| -> Result<i128, CovError> {
        match ctx.eval(e)? {
            Val::Int(n) => Ok(n),
            other => Err(CovError::BadValue {
                ctx: format!("bin {bin} repeat range"),
                got: format!("{other:?}"),
            }),
        }
    };
    let lo = get(ctx, &r.lo)?;
    let hi = match &r.hi {
        Some(e) => get(ctx, e)?,
        None => lo,
    };
    if lo < 0 || hi < lo {
        return Err(CovError::TransRepeat {
            bin: bin.to_string(),
            detail: format!("[{lo}:{hi}]"),
        });
    }
    if hi as u128 > MAX_REPEAT {
        return Err(CovError::TooManyValues {
            ctx: format!("bin {bin} repeat range"),
            limit: MAX_REPEAT,
        });
    }
    Ok((lo as u32, hi as u32))
}

/// Evaluates a bin's `trans_list` into one [`TransSeq`] per `trans_set`.
fn compile_trans_sets(
    ctx: &mut Ctx,
    b: &BinDecl,
    sets: &[TransSet],
) -> Result<Vec<TransSeq>, CovError> {
    let name = b.name.as_str();
    let mut out = Vec::with_capacity(sets.len());
    for set in sets {
        let mut seq: TransSeq = Vec::with_capacity(set.len());
        for item in set {
            let values = trans_item_values(ctx, name, b.wildcard, &item.values)?;
            let rep = match &item.rep {
                TransRep::Once => Rep::Once,
                TransRep::Consecutive(r) => {
                    let (lo, hi) = repeat_bounds(ctx, name, r)?;
                    Rep::Consec(lo, hi)
                }
                TransRep::Goto(r) => {
                    let (lo, hi) = repeat_bounds(ctx, name, r)?;
                    if lo == 0 {
                        return Err(CovError::TransRepeat {
                            bin: name.to_string(),
                            detail: "a goto repetition needs at least one occurrence".to_string(),
                        });
                    }
                    Rep::Goto(lo, hi)
                }
                TransRep::NonConsecutive(r) => {
                    let (lo, hi) = repeat_bounds(ctx, name, r)?;
                    Rep::NonConsec(lo, hi)
                }
            };
            seq.push(TransElem { set: values, rep });
        }
        if trans::min_samples(&seq) < 2 {
            return Err(CovError::TransZeroLength {
                bin: name.to_string(),
            });
        }
        out.push(seq);
    }
    Ok(out)
}

/// `alts` without whatever matches an ignored/illegal sequence.
fn apply_removals(alts: Vec<Alt>, removals: &[Alt]) -> Vec<Alt> {
    removals.iter().fold(alts, |alts, r| {
        alts.iter()
            .flat_map(|a| trans::remove_window(a, r))
            .collect()
    })
}

fn build_trans_bins(
    b: &BinDecl,
    seqs: &[TransSeq],
    removals: &[Alt],
) -> Result<Vec<Bin>, CovError> {
    let name = b.name.as_str();
    let remove = b.kind == BinKind::Normal && !removals.is_empty();
    let mk = |name: String, seqs: &[TransSeq]| -> Result<Bin, CovError> {
        let nfa = Nfa::compile(seqs)?;
        let max_len = seqs
            .iter()
            .map(|s| trans::max_samples(s))
            .max()
            .unwrap_or(0);
        let last = seqs
            .iter()
            .filter_map(|s| s.last())
            .fold(IntSet::new(), |acc, e| acc.union(&e.set));
        let tm = TransMatcher::new(nfa, max_len).with_last(last);
        let empty = tm.is_dead();
        let mut bin = Bin::new(name, b.kind, Matcher::Trans(tm), b.iff.clone());
        bin.empty = empty;
        Ok(bin)
    };
    match &b.array {
        ArrayKind::None if !remove => Ok(vec![mk(name.to_string(), seqs)?]),
        ArrayKind::None => {
            let mut alts = Vec::new();
            for s in seqs {
                if !trans::is_bounded(s) {
                    return Err(CovError::TransUnbounded {
                        bin: name.to_string(),
                        what: "a covered bin alongside ignore_bins or illegal_bins transitions",
                    });
                }
                alts.extend(trans::expand_alts(name, s)?);
            }
            let kept: Vec<TransSeq> = apply_removals(alts, removals)
                .into_iter()
                .map(alt_to_seq)
                .collect();
            Ok(vec![mk(name.to_string(), &kept)?])
        }
        ArrayKind::Open => {
            let mut seen = HashSet::new();
            let mut out = Vec::new();
            for s in seqs {
                if !trans::is_bounded(s) {
                    return Err(CovError::TransUnbounded {
                        bin: name.to_string(),
                        what: "a bin array ([])",
                    });
                }
                for alt in trans::expand_alts(name, s)? {
                    for vs in trans::value_seqs(name, &alt)? {
                        let label = vs
                            .iter()
                            .map(|v| v.to_string())
                            .collect::<Vec<_>>()
                            .join("=>");
                        if !seen.insert(label.clone()) {
                            continue;
                        }
                        let single: Alt = vs
                            .iter()
                            .map(|&v| IntSet::from_intervals([(v, v)]))
                            .collect();
                        let kept = if remove {
                            apply_removals(vec![single], removals)
                        } else {
                            vec![single]
                        };
                        let kept: Vec<TransSeq> = kept.into_iter().map(alt_to_seq).collect();
                        out.push(mk(format!("{name}[{label}]"), &kept)?);
                    }
                }
            }
            Ok(out)
        }
        ArrayKind::Fixed(_) => Err(CovError::Unsupported(format!(
            "bin {name}: a transition bin takes the [] form, not [N] (Syntax 19-3)"
        ))),
    }
}

// ---------------------------------------------------------------------------
// integral bins

/// Evaluates an integral bin value; `None` (with a warning) when it cannot
/// participate (19.5.7).
fn int_value(ctx: &mut Ctx, bin: &str, v: Val) -> Result<Option<i128>, CovError> {
    match v {
        Val::Int(i) => Ok(Some(i)),
        Val::Real(r) => {
            if r.is_finite() && r.fract() == 0.0 && r.abs() < 1e30 {
                Ok(Some(r as i128))
            } else {
                ctx.warn(
                    bin,
                    format!("value {r} is not representable by the coverpoint type"),
                );
                Ok(None)
            }
        }
        Val::Unknown | Val::Pat { .. } => {
            ctx.warn(bin, "value has x or z bits".to_string());
            Ok(None)
        }
        other => Err(CovError::BadValue {
            ctx: format!("bin {bin}"),
            got: format!("{other:?}"),
        }),
    }
}

fn int_items_to_seq(
    ctx: &mut Ctx,
    bin: &str,
    items: &[RangeItem],
) -> Result<Vec<(i128, i128)>, CovError> {
    let (dmin, dmax) = (ctx.ty.dmin(), ctx.ty.dmax());
    let mut seq = Vec::new();
    for item in items {
        match item {
            RangeItem::Single(e) => {
                let v = ctx.eval(e)?;
                push_single(ctx, bin, v, &mut seq)?;
            }
            RangeItem::Range(lo, hi) => {
                let lo = match lo {
                    Bound::Dollar => Some(dmin),
                    Bound::Expr(e) => {
                        let v = ctx.eval(e)?;
                        int_value(ctx, bin, v)?
                    }
                };
                let hi = match hi {
                    Bound::Dollar => Some(dmax),
                    Bound::Expr(e) => {
                        let v = ctx.eval(e)?;
                        int_value(ctx, bin, v)?
                    }
                };
                if let (Some(lo), Some(hi)) = (lo, hi) {
                    push_range(ctx, bin, lo, hi, &mut seq);
                }
            }
            RangeItem::Tolerance {
                center,
                tol,
                relative,
            } => {
                let c = ctx.eval(center)?;
                let t = ctx.eval(tol)?;
                if let Some((lo, hi)) = int_tolerance(ctx, bin, c, t, *relative)? {
                    push_range(ctx, bin, lo, hi, &mut seq);
                }
            }
        }
    }
    Ok(seq)
}

fn push_single(
    ctx: &mut Ctx,
    bin: &str,
    v: Val,
    seq: &mut Vec<(i128, i128)>,
) -> Result<(), CovError> {
    if let Some(i) = int_value(ctx, bin, v)? {
        if i < ctx.ty.dmin() || i > ctx.ty.dmax() {
            ctx.warn(
                bin,
                format!("value {i} is not expressible by the coverpoint type"),
            );
        } else {
            seq.push((i, i));
        }
    }
    Ok(())
}

/// 19.5.7: a range keeps the values the type can express.
fn push_range(ctx: &mut Ctx, bin: &str, lo: i128, hi: i128, seq: &mut Vec<(i128, i128)>) {
    if lo > hi {
        ctx.warn(bin, format!("range [{lo}:{hi}] is empty"));
        return;
    }
    let (dmin, dmax) = (ctx.ty.dmin(), ctx.ty.dmax());
    let (clo, chi) = (lo.max(dmin), hi.min(dmax));
    if clo > chi {
        ctx.warn(
            bin,
            format!("range [{lo}:{hi}] has no value expressible by the coverpoint type"),
        );
        return;
    }
    if (clo, chi) != (lo, hi) {
        ctx.warn(
            bin,
            format!("range [{lo}:{hi}] clipped to [{clo}:{chi}] by the coverpoint type"),
        );
    }
    seq.push((clo, chi));
}

/// 11.4.13: `[A +/- B]` is `[A-B : A+B]`, `[A +%- B]` is
/// `[A-A*B/100 : A+A*B/100]`, the tolerance truncated to the type of `A`.
fn int_tolerance(
    ctx: &mut Ctx,
    bin: &str,
    center: Val,
    tol: Val,
    relative: bool,
) -> Result<Option<(i128, i128)>, CovError> {
    let a = match center {
        Val::Int(a) => a,
        Val::Unknown | Val::Pat { .. } => {
            ctx.warn(bin, "tolerance centre has x or z bits".to_string());
            return Ok(None);
        }
        other => {
            return Err(CovError::Unsupported(format!(
                "bin {bin}: tolerance range on an integral coverpoint with centre {other:?}"
            )));
        }
    };
    let b = match tol {
        Val::Int(b) => b as f64,
        Val::Real(r) => r,
        Val::Unknown | Val::Pat { .. } => {
            ctx.warn(bin, "tolerance has x or z bits".to_string());
            return Ok(None);
        }
        other => {
            return Err(CovError::BadValue {
                ctx: format!("bin {bin} tolerance"),
                got: format!("{other:?}"),
            });
        }
    };
    let t = if relative {
        ((a as f64) * b / 100.0).trunc() as i128
    } else {
        b.trunc() as i128
    };
    let (lo, hi) = (a - t, a + t);
    Ok(Some(if lo <= hi { (lo, hi) } else { (hi, lo) }))
}

fn set_to_seq(ctx: &mut Ctx, bin: &str, e: &Expr) -> Result<Vec<(i128, i128)>, CovError> {
    let v = ctx.eval(e)?;
    let Val::List(vals) = v else {
        return Err(CovError::BadValue {
            ctx: format!("bin {bin} set expression"),
            got: format!("{v:?}"),
        });
    };
    let mut seq = Vec::new();
    for v in vals {
        push_single(ctx, bin, v, &mut seq)?;
    }
    Ok(seq)
}

/// A wildcard bin value as a `(bits, care)` pattern.
fn wild_patterns(
    ctx: &mut Ctx,
    bin: &str,
    items: &[RangeItem],
) -> Result<Vec<(u128, u128)>, CovError> {
    let mask = ctx.ty.mask();
    let mut out = Vec::new();
    for item in items {
        let RangeItem::Single(e) = item else {
            return Err(CovError::Unsupported(format!(
                "bin {bin}: ranges in a wildcard bin"
            )));
        };
        match ctx.eval(e)? {
            Val::Pat { bits, care } => out.push((bits & care & mask, care & mask)),
            Val::Int(i) => {
                if i < ctx.ty.dmin() || i > ctx.ty.dmax() {
                    ctx.warn(
                        bin,
                        format!("value {i} is not expressible by the coverpoint type"),
                    );
                } else {
                    out.push((ctx.ty.bits_of(i), mask));
                }
            }
            other => {
                return Err(CovError::BadValue {
                    ctx: format!("wildcard bin {bin}"),
                    got: format!("{other:?}"),
                });
            }
        }
    }
    Ok(out)
}

/// The values matching a pattern, ascending by bit pattern.
pub(super) fn expand_pattern(
    ty: &TypeInfo,
    bin: &str,
    bits: u128,
    care: u128,
) -> Result<Vec<i128>, CovError> {
    let dc = !care & ty.mask();
    let n = 1u128 << dc.count_ones();
    if n > EXPAND_LIMIT {
        return Err(CovError::TooManyValues {
            ctx: format!("wildcard bin {bin}"),
            limit: EXPAND_LIMIT,
        });
    }
    let mut out = Vec::with_capacity(n as usize);
    let mut sub: u128 = 0;
    loop {
        out.push(ty.value_of((bits & care) | sub));
        if sub == dc {
            break;
        }
        sub = (sub.wrapping_sub(dc)) & dc;
    }
    Ok(out)
}

fn seq_count(seq: &[(i128, i128)]) -> u128 {
    seq.iter()
        .map(|&(lo, hi)| (hi - lo) as u128 + 1)
        .fold(0, u128::saturating_add)
}

/// Splits `seq` into `n` consecutive groups per 19.5.1: `B = max(total/n, 1)`
/// values to each of the first bins, the remainder to the last.
fn distribute_ints(seq: &[(i128, i128)], n: usize) -> Vec<Vec<(i128, i128)>> {
    let total = seq_count(seq);
    let b = (total / n as u128).max(1);
    let (mut idx, mut off) = (0usize, 0u128);
    let mut remaining = total;
    let mut out = Vec::with_capacity(n);
    for i in 0..n {
        let mut want = if i == n - 1 {
            remaining
        } else {
            b.min(remaining)
        };
        remaining -= want;
        let mut group = Vec::new();
        while want > 0 && idx < seq.len() {
            let (lo, hi) = seq[idx];
            let count = (hi - lo) as u128 + 1;
            let take = (count - off).min(want);
            group.push((lo + off as i128, lo + off as i128 + take as i128 - 1));
            off += take;
            want -= take;
            if off == count {
                idx += 1;
                off = 0;
            }
        }
        out.push(group);
    }
    out
}

/// The same split for real items (each item counts one).
fn distribute_items<T: Clone>(items: &[T], n: usize) -> Vec<Vec<T>> {
    let total = items.len();
    let b = (total / n).max(1);
    (0..n)
        .map(|i| {
            let start = (i * b).min(total);
            let end = if i == n - 1 {
                total
            } else {
                ((i + 1) * b).min(total)
            };
            items[start..end].to_vec()
        })
        .collect()
}

fn expand_seq(bin: &str, seq: &[(i128, i128)]) -> Result<Vec<i128>, CovError> {
    if seq_count(seq) > EXPAND_LIMIT {
        return Err(CovError::TooManyValues {
            ctx: format!("bin {bin}"),
            limit: EXPAND_LIMIT,
        });
    }
    let mut out = Vec::new();
    for &(lo, hi) in seq {
        let mut v = lo;
        while v <= hi {
            out.push(v);
            v += 1;
        }
    }
    Ok(out)
}

fn filter_with(
    ctx: &mut Ctx,
    bin: &str,
    seq: &[(i128, i128)],
    with: &Expr,
) -> Result<Vec<(i128, i128)>, CovError> {
    let mut out = Vec::new();
    for v in expand_seq(bin, seq)? {
        if ctx.eval_with(with, v)? {
            out.push((v, v));
        }
    }
    Ok(out)
}

fn fixed_count(ctx: &mut Ctx, b: &BinDecl, e: &Expr) -> Result<usize, CovError> {
    let n = match ctx.eval(e)? {
        Val::Int(n) => n,
        other => {
            return Err(CovError::BadValue {
                ctx: format!("bin {} number of bins", b.name),
                got: format!("{other:?}"),
            });
        }
    };
    if n <= 0 {
        return Err(CovError::NonPositiveBins {
            bin: b.name.clone(),
            n,
        });
    }
    if n as u128 > EXPAND_LIMIT {
        return Err(CovError::TooManyValues {
            ctx: format!("bin {} number of bins", b.name),
            limit: EXPAND_LIMIT,
        });
    }
    Ok(n as usize)
}

fn build_int_bins(
    ctx: &mut Ctx,
    b: &BinDecl,
    body: &BinBody,
    distribute_first: bool,
) -> Result<Vec<Bin>, CovError> {
    let (items, with) = match body {
        BinBody::Ranges { items, with } => (Some(items), with.as_ref()),
        BinBody::Set(_) => (None, None),
        BinBody::Default | BinBody::DefaultSeq | BinBody::Trans(_) => {
            unreachable!("default and transition bins are built by their own builders")
        }
    };
    let name = b.name.as_str();
    let mk = |name: String, set: IntSet| Bin::new(name, b.kind, Matcher::Ints(set), b.iff.clone());

    // A plain wildcard bin keeps its patterns: nothing is expanded.
    if b.wildcard && b.array == ArrayKind::None && with.is_none() {
        let Some(items) = items else {
            return Err(CovError::Unsupported(format!(
                "bin {name}: wildcard with a set expression"
            )));
        };
        let pats = wild_patterns(ctx, name, items)?;
        return Ok(vec![Bin::new(
            name.to_string(),
            b.kind,
            Matcher::Pats(pats),
            b.iff.clone(),
        )]);
    }

    let seq = match (body, b.wildcard) {
        (BinBody::Ranges { items, .. }, true) => {
            let mut seq = Vec::new();
            for (bits, care) in wild_patterns(ctx, name, items)? {
                for v in expand_pattern(&ctx.ty, name, bits, care)? {
                    seq.push((v, v));
                }
            }
            seq
        }
        (BinBody::Ranges { items, .. }, false) => int_items_to_seq(ctx, name, items)?,
        (BinBody::Set(e), false) => set_to_seq(ctx, name, e)?,
        (BinBody::Set(_), true) => {
            return Err(CovError::Unsupported(format!(
                "bin {name}: wildcard with a set expression"
            )));
        }
        (BinBody::Default | BinBody::DefaultSeq | BinBody::Trans(_), _) => {
            unreachable!("default and transition bins are built by their own builders")
        }
    };

    match &b.array {
        ArrayKind::None => {
            let seq = match with {
                Some(w) => filter_with(ctx, name, &seq, w)?,
                None => seq,
            };
            Ok(vec![mk(name.to_string(), IntSet::from_intervals(seq))])
        }
        ArrayKind::Open => {
            let seq = match with {
                Some(w) => filter_with(ctx, name, &seq, w)?,
                None => seq,
            };
            let mut seen = HashSet::new();
            let mut out = Vec::new();
            for v in expand_seq(name, &seq)? {
                if seen.insert(v) {
                    out.push(mk(format!("{name}[{v}]"), IntSet::from_intervals([(v, v)])));
                }
            }
            Ok(out)
        }
        ArrayKind::Fixed(e) => {
            let n = fixed_count(ctx, b, e)?;
            let groups = match with {
                Some(w) if distribute_first => {
                    let mut gs = Vec::with_capacity(n);
                    for g in distribute_ints(&seq, n) {
                        gs.push(filter_with(ctx, name, &g, w)?);
                    }
                    gs
                }
                Some(w) => distribute_ints(&filter_with(ctx, name, &seq, w)?, n),
                None => distribute_ints(&seq, n),
            };
            Ok(groups
                .into_iter()
                .enumerate()
                .map(|(i, g)| mk(format!("{name}[{i}]"), IntSet::from_intervals(g)))
                .collect())
        }
    }
}

/// 19.5.3: automatic bins for a coverpoint with no explicit non-ignore,
/// non-illegal bins.
fn build_auto_bins(ctx: &Ctx, decl: &CoverpointDecl, opts: &Options) -> Vec<Bin> {
    let mk = |name: String, lo: i128, hi: i128| {
        Bin::new(
            name,
            BinKind::Normal,
            Matcher::Ints(IntSet::from_intervals([(lo, hi)])),
            None,
        )
    };
    if let Some(en) = &decl.enum_values {
        return en
            .iter()
            .map(|(n, v)| mk(format!("auto[{n}]"), *v, *v))
            .collect();
    }
    let (dmin, dmax) = (ctx.ty.dmin(), ctx.ty.dmax());
    let total = (dmax - dmin) as u128 + 1;
    let n = total.min(opts.auto_bin_max as u128).max(1);
    let b = total / n;
    let mut out = Vec::with_capacity(n as usize);
    for i in 0..n {
        let lo = dmin + (i * b) as i128;
        let hi = if i == n - 1 { dmax } else { lo + b as i128 - 1 };
        let name = if lo == hi {
            format!("auto[{lo}]")
        } else {
            format!("auto[{lo}:{hi}]")
        };
        out.push(mk(name, lo, hi));
    }
    out
}

// ---------------------------------------------------------------------------
// real bins

fn real_value(ctx: &mut Ctx, bin: &str, v: Val) -> Result<Option<f64>, CovError> {
    match v {
        Val::Real(r) => Ok(Some(r)),
        Val::Int(i) => Ok(Some(i as f64)),
        Val::Unknown | Val::Pat { .. } => {
            ctx.warn(bin, "value has x or z bits".to_string());
            Ok(None)
        }
        other => Err(CovError::BadValue {
            ctx: format!("bin {bin}"),
            got: format!("{other:?}"),
        }),
    }
}

/// Divides `[lo:hi]` into `interval`-sized intervals (19.5.1).
fn real_range_items(lo: f64, hi: f64, interval: f64, out: &mut Vec<RealItem>) {
    let n = ((hi - lo) / interval - 1e-9).ceil();
    if n.is_nan() || n <= 1.0 {
        out.push(RealItem {
            lo,
            hi,
            hi_closed: true,
        });
        return;
    }
    let n = n as usize;
    for i in 0..n {
        let a = lo + (i as f64) * interval;
        if i == n - 1 {
            out.push(RealItem {
                lo: a,
                hi,
                hi_closed: true,
            });
        } else {
            out.push(RealItem {
                lo: a,
                hi: lo + ((i + 1) as f64) * interval,
                hi_closed: false,
            });
        }
    }
}

fn real_items(
    ctx: &mut Ctx,
    bin: &str,
    body: &BinBody,
    interval: f64,
) -> Result<Vec<RealItem>, CovError> {
    let mut out = Vec::new();
    let single = |ctx: &mut Ctx, v: Val, out: &mut Vec<RealItem>| -> Result<(), CovError> {
        if let Some(r) = real_value(ctx, bin, v)? {
            out.push(RealItem {
                lo: r,
                hi: r,
                hi_closed: true,
            });
        }
        Ok(())
    };
    match body {
        BinBody::Set(e) => {
            let v = ctx.eval(e)?;
            let Val::List(vals) = v else {
                return Err(CovError::BadValue {
                    ctx: format!("bin {bin} set expression"),
                    got: format!("{v:?}"),
                });
            };
            for v in vals {
                single(ctx, v, &mut out)?;
            }
        }
        BinBody::Ranges { items, .. } => {
            for item in items {
                match item {
                    RangeItem::Single(e) => {
                        let v = ctx.eval(e)?;
                        single(ctx, v, &mut out)?;
                    }
                    RangeItem::Range(lo, hi) => {
                        let dollar = matches!(lo, Bound::Dollar) || matches!(hi, Bound::Dollar);
                        let end = |ctx: &mut Ctx, b: &Bound, inf: f64| match b {
                            Bound::Dollar => Ok(Some(inf)),
                            Bound::Expr(e) => {
                                let v = ctx.eval(e)?;
                                real_value(ctx, bin, v)
                            }
                        };
                        let lo = end(ctx, lo, f64::NEG_INFINITY)?;
                        let hi = end(ctx, hi, f64::INFINITY)?;
                        let (Some(lo), Some(hi)) = (lo, hi) else {
                            continue;
                        };
                        if lo > hi {
                            ctx.warn(bin, format!("range [{lo}:{hi}] is empty"));
                        } else if dollar {
                            // 19.5.1: a `$` range is one bin, never divided.
                            out.push(RealItem {
                                lo,
                                hi,
                                hi_closed: true,
                            });
                        } else {
                            real_range_items(lo, hi, interval, &mut out);
                        }
                    }
                    RangeItem::Tolerance {
                        center,
                        tol,
                        relative,
                    } => {
                        let c = ctx.eval(center)?;
                        let t = ctx.eval(tol)?;
                        let (Some(a), Some(b)) =
                            (real_value(ctx, bin, c)?, real_value(ctx, bin, t)?)
                        else {
                            continue;
                        };
                        let t = if *relative { (a * b / 100.0).abs() } else { b };
                        let (lo, hi) = (a - t, a + t);
                        let (lo, hi) = if lo <= hi { (lo, hi) } else { (hi, lo) };
                        real_range_items(lo, hi, interval, &mut out);
                    }
                }
            }
        }
        BinBody::Default | BinBody::DefaultSeq | BinBody::Trans(_) => {
            unreachable!("default and transition bins are built by their own builders")
        }
    }
    Ok(out)
}

fn build_real_bins(
    ctx: &mut Ctx,
    b: &BinDecl,
    body: &BinBody,
    interval: f64,
) -> Result<Vec<Bin>, CovError> {
    if b.wildcard {
        return Err(CovError::RealUnsupported {
            bin: b.name.clone(),
            what: "a wildcard bin",
        });
    }
    if let BinBody::Ranges { with: Some(_), .. } = body {
        return Err(CovError::RealUnsupported {
            bin: b.name.clone(),
            what: "a with clause",
        });
    }
    let name = b.name.as_str();
    let items = real_items(ctx, name, body, interval)?;
    let mk = |name: String, items: Vec<RealItem>| {
        Bin::new(name, b.kind, Matcher::Reals(items), b.iff.clone())
    };
    match &b.array {
        ArrayKind::None => Ok(vec![mk(name.to_string(), items)]),
        ArrayKind::Open => {
            let mut out: Vec<Bin> = Vec::new();
            let mut seen: Vec<RealItem> = Vec::new();
            for it in items {
                // identical intervals from several ranges are merged
                if seen.contains(&it) {
                    continue;
                }
                seen.push(it);
                out.push(mk(format!("{name}[{}", it.label()), vec![it]));
            }
            Ok(out)
        }
        ArrayKind::Fixed(e) => {
            let n = fixed_count(ctx, b, e)?;
            Ok(distribute_items(&items, n)
                .into_iter()
                .enumerate()
                .map(|(i, g)| mk(format!("{name}[{i}]"), g))
                .collect())
        }
    }
}

// ---------------------------------------------------------------------------
// post-processing

/// Flags bins that no value can reach once ignore/illegal values are removed
/// (19.5.5, 19.5.6).
fn mark_empty(ty: &TypeInfo, bins: &mut [Bin]) {
    let mut ex_ints = IntSet::new();
    let mut ex_pats: Vec<(u128, u128)> = Vec::new();
    for b in bins.iter() {
        if b.kind == BinKind::Normal {
            continue;
        }
        match &b.matcher {
            Matcher::Ints(s) => ex_ints = ex_ints.union(s),
            Matcher::Pats(p) => ex_pats.extend(p.iter().copied()),
            Matcher::Reals(_) | Matcher::Default | Matcher::Trans(_) | Matcher::DefaultSeq => {}
        }
    }
    let covered_by_pats = |v: i128| {
        let bits = ty.bits_of(v);
        ex_pats.iter().any(|&(pb, care)| (bits ^ pb) & care == 0)
    };
    for b in bins.iter_mut() {
        if b.kind != BinKind::Normal {
            continue;
        }
        b.empty = match &b.matcher {
            Matcher::Ints(s) => {
                let rest = s.subtract(&ex_ints);
                if rest.is_empty() {
                    true
                } else if ex_pats.is_empty() {
                    false
                } else {
                    match rest.values(EXPAND_LIMIT) {
                        Some(vs) => vs.into_iter().all(&covered_by_pats),
                        None => false,
                    }
                }
            }
            Matcher::Pats(p) => p.is_empty(),
            // Real bins: an empty item list is empty; exclusion by real
            // ignore bins is value-wise, so a populated bin stays populated.
            Matcher::Reals(r) => r.is_empty(),
            Matcher::Default | Matcher::DefaultSeq => false,
            // fixed when the bin was built (everything removed, or a value
            // set was empty); value ignores never touch a transition (19.5.5)
            Matcher::Trans(t) => t.is_dead(),
        };
    }
}

/// `detect_overlap` (19.7): a warning per pair of overlapping normal bins.
fn detect_overlap(cp: &str, bins: &[Bin], warns: &mut Vec<String>) {
    let normal: Vec<&Bin> = bins
        .iter()
        .filter(|b| b.kind == BinKind::Normal && !b.is_default())
        .collect();
    let mut pairs: Vec<(usize, usize)> = Vec::new();
    // integral bins: sweep over (lo, hi, bin) sorted by lo
    let mut ivs: Vec<(i128, i128, usize)> = Vec::new();
    for (i, b) in normal.iter().enumerate() {
        if let Matcher::Ints(s) = &b.matcher {
            ivs.extend(s.intervals().iter().map(|&(lo, hi)| (lo, hi, i)));
        }
    }
    ivs.sort_unstable();
    let mut active: Vec<(i128, usize)> = Vec::new(); // (hi, bin)
    for &(lo, hi, i) in &ivs {
        active.retain(|&(ahi, _)| ahi >= lo);
        for &(_, j) in &active {
            if j != i && !pairs.contains(&(j.min(i), j.max(i))) {
                pairs.push((j.min(i), j.max(i)));
            }
        }
        active.push((hi, i));
    }
    // real bins: pairwise
    for (i, a) in normal.iter().enumerate() {
        for (j, b) in normal.iter().enumerate().skip(i + 1) {
            if let (Matcher::Reals(x), Matcher::Reals(y)) = (&a.matcher, &b.matcher)
                && x.iter().any(|p| y.iter().any(|q| p.overlaps(q)))
                && !pairs.contains(&(i, j))
            {
                pairs.push((i, j));
            }
        }
    }
    pairs.sort_unstable();
    for (i, j) in pairs {
        warns.push(format!(
            "coverpoint {cp}: bins {} and {} overlap (detect_overlap)",
            normal[i].name, normal[j].name
        ));
    }
}