vj-sim 0.3.0

//! Transition bins (IEEE 1800-2023 19.5.2): sequences of coverpoint values at
//! successive sample points.
//!
//! A bin's `trans_list` is compiled once into a small NFA over sampled values.
//! The matcher keeps the set of states the recent samples left active, so
//! overlapping matches need no bookkeeping: a new attempt starts at every
//! sample, a bin counts at most once per sample however many attempts finish
//! on it (19.5.2), and a failed attempt simply drops out of the set.
//!
//! The pieces:
//! * [`TransSeq`] is one `trans_set` with its value sets and repetitions
//!   evaluated (`1,5 => 6,7`, `3[*3:5]`, `3[->2]`, `3[=2]`);
//! * [`expand_alts`] turns a bounded sequence into its alternatives (one value
//!   set per position), used for `b[]` arrays and for ignore/illegal removal;
//! * [`remove_window`] removes the part of a covered sequence that cannot be
//!   matched without also matching an ignored/illegal one (19.5.5, 19.5.6);
//! * [`TransMatcher`] runs the NFA.

use super::intset::IntSet;
use super::value::CovError;

/// Largest repeat count in a `[* ]`, `[-> ]` or `[= ]`.
pub const MAX_REPEAT: u128 = 1 << 16;
/// Largest NFA a bin may compile to.
pub const MAX_STATES: usize = 1 << 18;
/// Largest number of alternatives/sequences one bin expands to.
pub const MAX_ALTS: u128 = 1 << 22;

/// The repetition applied to one `trans_item` (all counts are inclusive).
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Rep {
    Once,
    /// `item [* lo:hi]`: consecutive repetition.
    Consec(u32, u32),
    /// `item [-> lo:hi]`: goto repetition.
    Goto(u32, u32),
    /// `item [= lo:hi]`: nonconsecutive repetition.
    NonConsec(u32, u32),
}

#[derive(Clone, Debug, PartialEq)]
pub struct TransElem {
    pub set: IntSet,
    pub rep: Rep,
}

/// One `trans_set`: `a => b[*2] => c`.
pub type TransSeq = Vec<TransElem>;

/// One bounded alternative: the set of values accepted at each position.
pub type Alt = Vec<IntSet>;

impl TransElem {
    pub fn once(set: IntSet) -> TransElem {
        TransElem {
            set,
            rep: Rep::Once,
        }
    }

    pub fn is_bounded(&self) -> bool {
        matches!(self.rep, Rep::Once | Rep::Consec(..))
    }

    /// The fewest samples the element consumes.
    fn min_samples(&self) -> u64 {
        match self.rep {
            Rep::Once => 1,
            Rep::Consec(lo, _) | Rep::Goto(lo, _) | Rep::NonConsec(lo, _) => lo as u64,
        }
    }
}

/// `true` when every element has a fixed set of lengths (no goto or
/// nonconsecutive repetition).
pub fn is_bounded(seq: &[TransElem]) -> bool {
    seq.iter().all(TransElem::is_bounded)
}

/// The fewest samples the sequence spans; a transition needs two (19.5.2:
/// "transition bin specifications of length 0 shall be illegal").
pub fn min_samples(seq: &[TransElem]) -> u64 {
    seq.iter().map(TransElem::min_samples).sum()
}

/// The longest bounded alternative of `seq` in samples (0 when unbounded).
pub fn max_samples(seq: &[TransElem]) -> usize {
    let mut n = 0usize;
    for e in seq {
        match e.rep {
            Rep::Once => n += 1,
            Rep::Consec(_, hi) => n += hi as usize,
            Rep::Goto(..) | Rep::NonConsec(..) => return 0,
        }
    }
    n
}

/// Every alternative of a bounded sequence, repetition counts unrolled.
pub fn expand_alts(bin: &str, seq: &[TransElem]) -> Result<Vec<Alt>, CovError> {
    let mut alts: Vec<Alt> = vec![Vec::new()];
    for e in seq {
        let counts: Vec<u32> = match e.rep {
            Rep::Once => vec![1],
            Rep::Consec(lo, hi) => (lo..=hi).collect(),
            Rep::Goto(..) | Rep::NonConsec(..) => {
                return Err(CovError::TransUnbounded {
                    bin: bin.to_string(),
                    what: "an alternative list",
                });
            }
        };
        if alts.len() as u128 * counts.len() as u128 > MAX_ALTS {
            return Err(CovError::TooManyValues {
                ctx: format!("transition bin {bin}"),
                limit: MAX_ALTS,
            });
        }
        let mut next = Vec::with_capacity(alts.len() * counts.len());
        for a in &alts {
            for &c in &counts {
                let mut a = a.clone();
                for _ in 0..c {
                    a.push(e.set.clone());
                }
                next.push(a);
            }
        }
        alts = next;
    }
    Ok(alts)
}

/// Every value sequence an alternative stands for, first position outermost
/// (`1,5 => 6,7` is `1=>6, 1=>7, 5=>6, 5=>7`).
pub fn value_seqs(bin: &str, alt: &Alt) -> Result<Vec<Vec<i128>>, CovError> {
    let mut total: u128 = 1;
    for s in alt {
        total = total.saturating_mul(s.count());
    }
    if total > MAX_ALTS {
        return Err(CovError::TooManyValues {
            ctx: format!("transition bin {bin}"),
            limit: MAX_ALTS,
        });
    }
    let mut out: Vec<Vec<i128>> = vec![Vec::new()];
    for s in alt {
        let vals = s.values(MAX_ALTS).ok_or_else(|| CovError::TooManyValues {
            ctx: format!("transition bin {bin}"),
            limit: MAX_ALTS,
        })?;
        let mut next = Vec::with_capacity(out.len() * vals.len());
        for prefix in &out {
            for &v in &vals {
                let mut p = prefix.clone();
                p.push(v);
                next.push(p);
            }
        }
        out = next;
    }
    Ok(out)
}

/// The members of both `a` and `b`.
fn intersect(a: &IntSet, b: &IntSet) -> IntSet {
    a.subtract(&a.subtract(b))
}

/// The part of `alt` that matches without matching `ign` anywhere inside it.
/// (19.5.5: "the ignored sequence 2=>3 would remove the covered sequence
/// 1=>2=>3=>4".) The result is a union of alternatives.
pub fn remove_window(alt: &Alt, ign: &Alt) -> Vec<Alt> {
    let (n, m) = (alt.len(), ign.len());
    if m == 0 || m > n {
        return vec![alt.clone()];
    }
    let mut work = vec![alt.clone()];
    for k in 0..=(n - m) {
        let mut next = Vec::new();
        for w in work {
            if !(0..m).all(|j| w[k + j].intersects(&ign[j])) {
                next.push(w);
                continue;
            }
            // w minus (matches ign at offset k): split on the first position
            // where the value leaves the ignored set.
            for j in 0..m {
                let mut p = w.clone();
                for i in 0..j {
                    p[k + i] = intersect(&w[k + i], &ign[i]);
                }
                p[k + j] = w[k + j].subtract(&ign[j]);
                if p.iter().all(|s| !s.is_empty()) {
                    next.push(p);
                }
            }
        }
        work = next;
    }
    work
}

pub fn alt_to_seq(alt: Alt) -> TransSeq {
    alt.into_iter().map(TransElem::once).collect()
}

// ---------------------------------------------------------------------------
// NFA

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Label {
    /// The sample is in set `i`.
    In(usize),
    /// The sample is not in set `i` (the "..." of goto/nonconsecutive).
    NotIn(usize),
}

#[derive(Default)]
struct Builder {
    edges: Vec<Vec<(Label, usize)>>,
    eps: Vec<Vec<usize>>,
    finals: Vec<bool>,
    sets: Vec<IntSet>,
}

impl Builder {
    fn state(&mut self) -> Result<usize, CovError> {
        if self.edges.len() >= MAX_STATES {
            return Err(CovError::TooManyValues {
                ctx: "transition bin states".to_string(),
                limit: MAX_STATES as u128,
            });
        }
        self.edges.push(Vec::new());
        self.eps.push(Vec::new());
        self.finals.push(false);
        Ok(self.edges.len() - 1)
    }

    fn set(&mut self, s: &IntSet) -> usize {
        if let Some(i) = self.sets.iter().position(|x| x == s) {
            return i;
        }
        self.sets.push(s.clone());
        self.sets.len() - 1
    }

    fn edge(&mut self, from: usize, l: Label, to: usize) {
        self.edges[from].push((l, to));
    }

    fn epsilon(&mut self, from: usize, to: usize) {
        self.eps[from].push(to);
    }

    fn add_seq(&mut self, seq: &[TransElem]) -> Result<(), CovError> {
        let mut cur = 0usize;
        for (idx, e) in seq.iter().enumerate() {
            // the start state is re-entered at every sample, so a leading
            // "any number of samples before the first occurrence" is free
            let at_start = idx == 0;
            let set = self.set(&e.set);
            let end = self.state()?;
            match e.rep {
                Rep::Once => {
                    self.edge(cur, Label::In(set), end);
                }
                Rep::Consec(lo, hi) => {
                    let mut s = cur;
                    if lo == 0 {
                        self.epsilon(cur, end);
                    }
                    for k in 1..=hi {
                        let n = self.state()?;
                        self.edge(s, Label::In(set), n);
                        if k >= lo {
                            self.epsilon(n, end);
                        }
                        s = n;
                    }
                }
                Rep::Goto(lo, hi) | Rep::NonConsec(lo, hi) => {
                    let non_consec = matches!(e.rep, Rep::NonConsec(..));
                    // `[= n]` followed by another element waits for that
                    // element's first value: "followed sometime later by a 5"
                    // is the first 5 (the 19.5.2 `b7` example increments once,
                    // on the 13th sample, not on every later 5). As the last
                    // element there is nothing to wait for and `[= n]` ends on
                    // the n-th..m-th occurrence exactly like `[-> n]`.
                    let wait = match (non_consec, seq.get(idx + 1)) {
                        (true, Some(next)) => Some(self.set(&e.set.union(&next.set))),
                        _ => None,
                    };
                    // `n` is the state just after the k-th occurrence. It is
                    // never final-adjacent itself: waiting for the next
                    // occurrence happens in the separate state `w`, so an
                    // attempt does not re-match on every non-matching sample.
                    let mut n = cur;
                    for k in 0..=hi {
                        if k >= lo {
                            match wait {
                                Some(w) => {
                                    let t = self.state()?;
                                    self.epsilon(n, t);
                                    self.edge(t, Label::NotIn(w), t);
                                    self.epsilon(t, end);
                                }
                                None => self.epsilon(n, end),
                            }
                        }
                        if k < hi {
                            let mut w = n;
                            if !(k == 0 && at_start) {
                                w = self.state()?;
                                self.epsilon(n, w);
                                self.edge(w, Label::NotIn(set), w);
                            }
                            let next_n = self.state()?;
                            self.edge(w, Label::In(set), next_n);
                            n = next_n;
                        }
                    }
                }
            }
            cur = end;
        }
        self.finals[cur] = true;
        Ok(())
    }

    fn finish(self) -> Nfa {
        let n = self.edges.len();
        let mut closure = Vec::with_capacity(n);
        for s in 0..n {
            let mut seen = vec![false; n];
            let mut stack = vec![s];
            seen[s] = true;
            while let Some(x) = stack.pop() {
                for &y in &self.eps[x] {
                    if !seen[y] {
                        seen[y] = true;
                        stack.push(y);
                    }
                }
            }
            closure.push((0..n).filter(|&i| seen[i]).collect::<Vec<usize>>());
        }
        Nfa {
            edges: self.edges,
            closure,
            finals: self.finals,
            sets: self.sets,
        }
    }
}

#[derive(Clone, Debug, PartialEq)]
pub struct Nfa {
    edges: Vec<Vec<(Label, usize)>>,
    /// Epsilon closure of each state (including itself).
    closure: Vec<Vec<usize>>,
    finals: Vec<bool>,
    sets: Vec<IntSet>,
}

impl Nfa {
    /// One NFA accepting any of `seqs` (a bin's `trans_list`).
    pub fn compile(seqs: &[TransSeq]) -> Result<Nfa, CovError> {
        let mut b = Builder::default();
        b.state()?; // state 0: the start
        for s in seqs {
            b.add_seq(s)?;
        }
        Ok(b.finish())
    }

    pub fn states(&self) -> usize {
        self.edges.len()
    }

    fn label_matches(&self, l: Label, v: i128) -> bool {
        match l {
            Label::In(i) => self.sets[i].contains(v),
            Label::NotIn(i) => !self.sets[i].contains(v),
        }
    }

    /// Whether some input can reach a final state (no empty value set blocks
    /// every path).
    pub fn can_accept(&self) -> bool {
        let n = self.edges.len();
        let mut seen = vec![false; n];
        let mut stack: Vec<usize> = self.closure[0].clone();
        for &s in &stack {
            seen[s] = true;
        }
        while let Some(s) = stack.pop() {
            if self.finals[s] {
                return true;
            }
            for &(l, t) in &self.edges[s] {
                let live = match l {
                    Label::In(i) => !self.sets[i].is_empty(),
                    Label::NotIn(_) => true,
                };
                if live {
                    for &c in &self.closure[t] {
                        if !seen[c] {
                            seen[c] = true;
                            stack.push(c);
                        }
                    }
                }
            }
        }
        false
    }
}

/// What one sample did to a transition bin.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Step {
    /// A complete sequence matched at this sample.
    pub matched: bool,
    /// An attempt that began at an earlier sample is still alive.
    pub pending: bool,
}

/// A transition bin's matcher: the NFA and the attempts alive between samples.
#[derive(Clone, Debug, PartialEq)]
pub struct TransMatcher {
    nfa: Nfa,
    active: Vec<bool>,
    /// Samples spanned by the longest bounded alternative (0 if unbounded).
    pub max_len: usize,
    dead: bool,
    /// The values a sequence can end on: `binsof` of a transition bin uses the
    /// last value of the transition (19.6.1.1).
    pub last: IntSet,
}

impl TransMatcher {
    pub fn new(nfa: Nfa, max_len: usize) -> TransMatcher {
        let dead = !nfa.can_accept();
        let active = vec![false; nfa.states()];
        TransMatcher {
            nfa,
            active,
            max_len,
            dead,
            last: IntSet::new(),
        }
    }

    /// Records the values the sequences end on (see [`TransMatcher::last`]).
    pub fn with_last(mut self, last: IntSet) -> TransMatcher {
        self.last = last;
        self
    }

    /// No sequence can ever match (everything was removed, or a value set is
    /// empty). Such a bin is excluded from coverage (19.5.5).
    pub fn is_dead(&self) -> bool {
        self.dead
    }

    /// Drops every attempt in flight (a sample that breaks the sequence).
    pub fn clear(&mut self) {
        self.active.iter_mut().for_each(|a| *a = false);
    }

    /// Feeds the next sampled value.
    pub fn step(&mut self, v: i128) -> Step {
        let n = self.nfa.states();
        let mut cont = vec![false; n];
        for s in 0..n {
            if self.active[s] {
                self.advance(s, v, &mut cont);
            }
        }
        let pending = (0..n).any(|s| cont[s] && !self.nfa.edges[s].is_empty());
        let mut next = cont;
        for &s in &self.nfa.closure[0] {
            self.advance(s, v, &mut next);
        }
        let matched = (0..n).any(|s| next[s] && self.nfa.finals[s]);
        self.active = next;
        Step { matched, pending }
    }

    fn advance(&self, s: usize, v: i128, into: &mut [bool]) {
        for &(l, t) in &self.nfa.edges[s] {
            if self.nfa.label_matches(l, v) {
                for &c in &self.nfa.closure[t] {
                    into[c] = true;
                }
            }
        }
    }
}