vj_sim/constraints/
func.rs

1//! Functions called from constraints (task C13; IEEE 1800-2023 18.5.11).
2//!
3//! # What is here
4//!
5//! A constraint may call a function (`length == count_ones(v)`). The LRM calls
6//! it *before* the constraints are solved and treats its return value as a
7//! state variable, so the solver never has to look inside it: the call is
8//! evaluated once its arguments are known and replaced by the constant it
9//! returns ([`fold_ground_calls`]). Which arguments are known when is the
10//! business of [`super::func_order`] (an argument that is a random variable is
11//! solved first).
12//!
13//! The function itself is a [`Func`]: the builder translates the body of the
14//! SystemVerilog function into a small structured statement language over the
15//! constraint IR's own expressions, and [`call`] interprets it. The body's
16//! expressions are ordinary [`Expr`]s whose `Var(i)` is slot `i` of the call's
17//! *frame* (formals, then locals, then the result variable), so the whole
18//! operator semantics (widths, signedness, shifts, division) is the one the
19//! constraints already use. State variables (a non-`rand` property the body
20//! reads) are the program's, read before the solve like any other.
21//!
22//! # Restrictions (all loud, at build time)
23//!
24//! The builder refuses what LRM 18.5.11 forbids (`output`/`inout`/non-`const`
25//! `ref` formals, `rand_mode`/`constraint_mode`, state kept across calls) and
26//! what this interpreter does not model (strings, reals, aggregates, tasks,
27//! system calls other than constant ones, timing). A body that reads a random
28//! variable of the object other than through an argument is refused: the LRM
29//! gives such a read no meaning (the call precedes the solve).
30//!
31//! Locals are two-state here: a 4-state local starts at 0 rather than `x`
32//! (the same 2-state view the constraint solver takes of every value).
33//!
34//! # Limits
35//!
36//! A call runs at most [`MAX_STEPS`] statements and nests at most
37//! [`MAX_DEPTH`] calls deep; past either, the call fails with a
38//! [`FuncError`] instead of hanging the simulation on a runaway loop.
39
40use super::ir::{ArrayNode, Assignment, ConstraintEvalError, Expr, FuncId, Ty, eval, mask};
41use num_bigint::BigUint;
42use num_traits::Zero;
43use std::fmt;
44
45/// The most statements one top-level call may execute.
46pub const MAX_STEPS: u64 = 1 << 22;
47/// The deepest nesting of calls (a function calling functions).
48pub const MAX_DEPTH: usize = 64;
49
50/// One statement of a function body.
51#[derive(Clone, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
52pub enum Stmt {
53    /// `slot = expr`; the expression already has the slot's type.
54    Assign(u32, Expr),
55    /// `if (cond) then else otherwise` (a case statement is built as a chain).
56    If(Expr, Vec<Stmt>, Vec<Stmt>),
57    /// A loop. With `test_first` the condition is tested before every
58    /// iteration (`while`, `for`); without it, after every iteration but not
59    /// before the first (`do ... while`). `step` runs after each iteration,
60    /// also one ended by `continue` (a `for`'s step expressions). No `cond` is
61    /// an endless loop (`forever`, `for (;;)`).
62    Loop {
63        /// The loop condition.
64        cond: Option<Expr>,
65        /// The loop body.
66        body: Vec<Stmt>,
67        /// The step run after the body.
68        step: Vec<Stmt>,
69        /// Whether the condition guards the first iteration too.
70        test_first: bool,
71    },
72    /// `break`.
73    Break,
74    /// `continue`.
75    Continue,
76    /// `return`: the result variable already holds the value.
77    Return,
78}
79
80/// A function of a [`super::registry::Program`].
81#[derive(Clone, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
82pub struct Func {
83    /// Its declared name (diagnostics).
84    pub name: String,
85    /// The type of every frame slot: the formals (`n_params` of them, in
86    /// declaration order), the locals, then the result variable at [`Self::ret`].
87    pub slots: Vec<Ty>,
88    /// How many leading slots are formals.
89    pub n_params: usize,
90    /// The slot of the result variable (the function's own name).
91    pub ret: u32,
92    /// The body.
93    pub body: Vec<Stmt>,
94}
95
96/// Why a call failed.
97#[derive(Clone, Debug, PartialEq, Eq)]
98pub enum FuncError {
99    /// An expression of the body (or an argument) could not be evaluated.
100    Eval(ConstraintEvalError),
101    /// A call names no function, or passes the wrong number of arguments (a
102    /// malformed program).
103    Malformed(&'static str),
104    /// The nesting of calls exceeded [`MAX_DEPTH`].
105    TooDeep {
106        /// The function being entered.
107        func: String,
108    },
109    /// The call executed more than [`MAX_STEPS`] statements.
110    StepLimit {
111        /// The function that was running.
112        func: String,
113    },
114}
115
116impl fmt::Display for FuncError {
117    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
118        match self {
119            FuncError::Eval(e) => write!(f, "a function called from a constraint failed: {e}"),
120            FuncError::Malformed(w) => write!(f, "malformed function call in a constraint: {w}"),
121            FuncError::TooDeep { func } => write!(
122                f,
123                "function `{func}` called from a constraint nests calls deeper than {MAX_DEPTH}"
124            ),
125            FuncError::StepLimit { func } => write!(
126                f,
127                "function `{func}` called from a constraint ran more than {MAX_STEPS} statements \
128                 (a runaway loop?)"
129            ),
130        }
131    }
132}
133
134impl std::error::Error for FuncError {}
135
136impl From<ConstraintEvalError> for FuncError {
137    fn from(e: ConstraintEvalError) -> Self {
138        FuncError::Eval(e)
139    }
140}
141
142/// How a statement list ended.
143#[derive(Clone, Copy, PartialEq, Eq)]
144enum Flow {
145    Normal,
146    Break,
147    Continue,
148    Return,
149}
150
151struct Machine<'a> {
152    funcs: &'a [Func],
153    /// The state values; `vars` is the frame of the call being run.
154    asg: Assignment,
155    steps: u64,
156}
157
158impl Machine<'_> {
159    fn func(&self, id: FuncId) -> Result<&Func, FuncError> {
160        self.funcs.get(id as usize).ok_or(FuncError::Malformed(
161            "a call of a function outside the table",
162        ))
163    }
164
165    /// `e` with every nested call evaluated (against the current frame).
166    fn resolve(&mut self, e: &Expr, depth: usize) -> Result<Expr, FuncError> {
167        if !has_call(e) {
168            return Ok(e.clone());
169        }
170        match e {
171            Expr::Array(ArrayNode::Call { func, args, ty }) => {
172                let mut vals = Vec::with_capacity(args.len());
173                for a in args {
174                    vals.push(self.eval_in(a, depth)?);
175                }
176                let r = self.run(*func, vals, depth + 1)?;
177                Ok(Expr::Const(*ty, r))
178            }
179            // A virtual call through a handle (LRM 8.20): only the element the
180            // handle's dynamic class selects runs; the others may read members
181            // the object does not have.
182            Expr::Array(ArrayNode::Pick {
183                index, low, elems, ..
184            }) => {
185                let i = self.eval_in(index, depth)?;
186                let pos = i64::try_from(&i)
187                    .ok()
188                    .and_then(|i| i.checked_sub(*low))
189                    .and_then(|p| usize::try_from(p).ok())
190                    .filter(|&p| p < elems.len())
191                    .ok_or(FuncError::Malformed(
192                        "a virtual call on a handle whose class implements no such function",
193                    ))?;
194                self.resolve(&elems[pos], depth)
195            }
196            other => other.try_map_children(&mut |c| self.resolve(c, depth)),
197        }
198    }
199
200    fn eval_in(&mut self, e: &Expr, depth: usize) -> Result<BigUint, FuncError> {
201        let r = self.resolve(e, depth)?;
202        Ok(eval(&r, &self.asg)?)
203    }
204
205    fn run(&mut self, id: FuncId, args: Vec<BigUint>, depth: usize) -> Result<BigUint, FuncError> {
206        let (n_params, ret, slots, name) = {
207            let f = self.func(id)?;
208            (f.n_params, f.ret, f.slots.clone(), f.name.clone())
209        };
210        if depth >= MAX_DEPTH {
211            return Err(FuncError::TooDeep { func: name });
212        }
213        if args.len() != n_params {
214            return Err(FuncError::Malformed(
215                "a call with the wrong number of arguments",
216            ));
217        }
218        let mut frame: Vec<BigUint> = vec![BigUint::zero(); slots.len()];
219        for (k, a) in args.into_iter().enumerate() {
220            frame[k] = a & mask(slots[k].width);
221        }
222        let saved = std::mem::replace(&mut self.asg.vars, frame);
223        let body = self.func(id)?.body.clone();
224        let flow = self.exec(&body, id, depth);
225        let frame = std::mem::replace(&mut self.asg.vars, saved);
226        flow?;
227        Ok(frame[ret as usize].clone() & mask(slots[ret as usize].width))
228    }
229
230    fn tick(&mut self, id: FuncId) -> Result<(), FuncError> {
231        self.steps += 1;
232        if self.steps > MAX_STEPS {
233            return Err(FuncError::StepLimit {
234                func: self.func(id)?.name.clone(),
235            });
236        }
237        Ok(())
238    }
239
240    fn exec(&mut self, body: &[Stmt], id: FuncId, depth: usize) -> Result<Flow, FuncError> {
241        for s in body {
242            self.tick(id)?;
243            match s {
244                Stmt::Assign(slot, e) => {
245                    let v = self.eval_in(e, depth)?;
246                    let w = self
247                        .func(id)?
248                        .slots
249                        .get(*slot as usize)
250                        .ok_or(FuncError::Malformed(
251                            "an assignment to a slot outside the frame",
252                        ))?
253                        .width;
254                    self.asg.vars[*slot as usize] = v & mask(w);
255                }
256                Stmt::If(c, t, e) => {
257                    let taken = !self.eval_in(c, depth)?.is_zero();
258                    let flow = self.exec(if taken { t } else { e }, id, depth)?;
259                    if flow != Flow::Normal {
260                        return Ok(flow);
261                    }
262                }
263                Stmt::Loop {
264                    cond,
265                    body,
266                    step,
267                    test_first,
268                } => {
269                    let mut first = true;
270                    loop {
271                        self.tick(id)?;
272                        if (*test_first || !first)
273                            && let Some(c) = cond
274                            && self.eval_in(c, depth)?.is_zero()
275                        {
276                            break;
277                        }
278                        first = false;
279                        match self.exec(body, id, depth)? {
280                            Flow::Break => break,
281                            Flow::Return => return Ok(Flow::Return),
282                            Flow::Normal | Flow::Continue => {}
283                        }
284                        if self.exec(step, id, depth)? == Flow::Return {
285                            return Ok(Flow::Return);
286                        }
287                    }
288                }
289                Stmt::Break => return Ok(Flow::Break),
290                Stmt::Continue => return Ok(Flow::Continue),
291                Stmt::Return => return Ok(Flow::Return),
292            }
293        }
294        Ok(Flow::Normal)
295    }
296}
297
298/// Whether `e` holds a function call.
299pub fn has_call(e: &Expr) -> bool {
300    e.any_node(&mut |n| matches!(n, Expr::Array(ArrayNode::Call { .. })))
301}
302
303/// Calls function `id` of `funcs` with the argument values `args` (each below
304/// `2^width` of its formal) and returns its result, reading the non-`rand`
305/// variables the body uses from `states`.
306pub fn call(
307    funcs: &[Func],
308    id: FuncId,
309    args: &[BigUint],
310    states: &[Option<BigUint>],
311) -> Result<BigUint, FuncError> {
312    let mut m = Machine {
313        funcs,
314        asg: Assignment {
315            vars: Vec::new(),
316            states: states.to_vec(),
317        },
318        steps: 0,
319    };
320    m.run(id, args.to_vec(), 0)
321}
322
323/// Whether `e` holds neither a random variable nor an array-level node: its
324/// value is fixed.
325fn is_ground(e: &Expr) -> bool {
326    !e.any_node(&mut |n| matches!(n, Expr::Var(..) | Expr::Array(_)))
327}
328
329/// `e` with every call whose arguments are already fixed (no random variable,
330/// no array-level node left in them) replaced by the constant it returns. A
331/// call with a still-unknown argument stays, its own arguments folded as far as
332/// they go.
333pub fn fold_ground_calls(
334    e: &Expr,
335    funcs: &[Func],
336    states: &[Option<BigUint>],
337) -> Result<Expr, FuncError> {
338    if !has_call(e) {
339        return Ok(e.clone());
340    }
341    match e {
342        Expr::Array(ArrayNode::Call { func, args, ty }) => {
343            let args = args
344                .iter()
345                .map(|a| fold_ground_calls(a, funcs, states))
346                .collect::<Result<Vec<_>, _>>()?;
347            if args.iter().all(is_ground) {
348                let asg = Assignment {
349                    vars: Vec::new(),
350                    states: states.to_vec(),
351                };
352                let vals = args
353                    .iter()
354                    .map(|a| eval(a, &asg))
355                    .collect::<Result<Vec<_>, _>>()?;
356                let r = call(funcs, *func, &vals, states)?;
357                Ok(Expr::Const(*ty, r))
358            } else {
359                Ok(Expr::Array(ArrayNode::Call {
360                    func: *func,
361                    args,
362                    ty: *ty,
363                }))
364            }
365        }
366        // Only the picked element is ever evaluated (a virtual call through a
367        // handle holds a call per possible class; the others may read members the
368        // object does not have), so the elements wait for the expansion.
369        Expr::Array(ArrayNode::Pick {
370            index,
371            low,
372            elems,
373            ty,
374        }) => Ok(Expr::Array(ArrayNode::Pick {
375            index: Box::new(fold_ground_calls(index, funcs, states)?),
376            low: *low,
377            elems: elems.clone(),
378            ty: *ty,
379        })),
380        other => other.try_map_children(&mut |c| fold_ground_calls(c, funcs, states)),
381    }
382}
383
384#[cfg(test)]
385pub(crate) mod tests {
386    use super::*;
387    use crate::constraints::ir::{BinOp, UnOp};
388
389    fn u(w: u32) -> Ty {
390        Ty::unsigned(w)
391    }
392    fn s32() -> Ty {
393        Ty::signed(32)
394    }
395    fn var(i: u32, t: Ty) -> Expr {
396        Expr::Var(i, t)
397    }
398    fn k(t: Ty, v: u64) -> Expr {
399        Expr::constant(t, v)
400    }
401    fn bin(op: BinOp, a: Expr, b: Expr, t: Ty) -> Expr {
402        Expr::Binary(op, Box::new(a), Box::new(b), t)
403    }
404    fn n(v: u64) -> BigUint {
405        BigUint::from(v)
406    }
407
408    /// LRM 18.5.11's `count_ones`:
409    /// `for (count_ones = 0; w != 0; w = w >> 1) count_ones += w & 1'b1;`
410    pub(crate) fn count_ones() -> Func {
411        // slots: 0 = w (10 bits), 1 = count_ones (32 bits)
412        let w = var(0, u(10));
413        let c = var(1, s32());
414        Func {
415            name: "count_ones".into(),
416            slots: vec![u(10), s32()],
417            n_params: 1,
418            ret: 1,
419            body: vec![
420                Stmt::Assign(1, k(s32(), 0)),
421                Stmt::Loop {
422                    cond: Some(bin(BinOp::Ne, w.clone(), k(u(10), 0), Ty::BIT)),
423                    body: vec![Stmt::Assign(
424                        1,
425                        bin(
426                            BinOp::Add,
427                            c.clone(),
428                            Expr::Resize(
429                                Box::new(bin(BinOp::And, w.clone(), k(u(10), 1), u(10))),
430                                s32(),
431                            ),
432                            s32(),
433                        ),
434                    )],
435                    step: vec![Stmt::Assign(
436                        0,
437                        bin(BinOp::Shr, w.clone(), k(u(32), 1), u(10)),
438                    )],
439                    test_first: true,
440                },
441            ],
442        }
443    }
444
445    #[test]
446    fn count_ones_counts_the_set_bits() {
447        let f = [count_ones()];
448        for v in [0u64, 1, 0b1011, 0x3ff, 0b10_0000_0001] {
449            let r = call(&f, 0, &[n(v)], &[]).unwrap();
450            assert_eq!(r, n(u64::from(v.count_ones())), "count_ones({v:#b})");
451        }
452    }
453
454    #[test]
455    fn a_runaway_loop_is_a_loud_error_not_a_hang() {
456        let f = [Func {
457            name: "spin".into(),
458            slots: vec![s32()],
459            n_params: 0,
460            ret: 0,
461            body: vec![Stmt::Loop {
462                cond: None,
463                body: Vec::new(),
464                step: Vec::new(),
465                test_first: true,
466            }],
467        }];
468        assert!(matches!(
469            call(&f, 0, &[], &[]),
470            Err(FuncError::StepLimit { .. })
471        ));
472    }
473
474    #[test]
475    fn recursion_works_and_unbounded_recursion_is_an_error() {
476        // fact(n) = n <= 1 ? 1 : n * fact(n - 1); slots: 0 = n, 1 = fact
477        let rec = Expr::Array(ArrayNode::Call {
478            func: 0,
479            args: vec![bin(BinOp::Sub, var(0, s32()), k(s32(), 1), s32())],
480            ty: s32(),
481        });
482        let fact = Func {
483            name: "fact".into(),
484            slots: vec![s32(), s32()],
485            n_params: 1,
486            ret: 1,
487            body: vec![Stmt::If(
488                bin(BinOp::Le, var(0, s32()), k(s32(), 1), Ty::BIT),
489                vec![Stmt::Assign(1, k(s32(), 1)), Stmt::Return],
490                vec![Stmt::Assign(1, bin(BinOp::Mul, var(0, s32()), rec, s32()))],
491            )],
492        };
493        assert_eq!(
494            call(std::slice::from_ref(&fact), 0, &[n(5)], &[]).unwrap(),
495            n(120)
496        );
497        let endless = Func {
498            body: vec![Stmt::Assign(
499                1,
500                Expr::Array(ArrayNode::Call {
501                    func: 0,
502                    args: vec![var(0, s32())],
503                    ty: s32(),
504                }),
505            )],
506            ..fact
507        };
508        assert!(matches!(
509            call(&[endless], 0, &[n(1)], &[]),
510            Err(FuncError::TooDeep { .. })
511        ));
512    }
513
514    #[test]
515    fn break_continue_and_do_while_follow_the_loop_rules() {
516        // r = 0; do { i++; if (i == 2) continue; if (i == 5) break; r += i; } while (i < 100);
517        // slots: 0 = i, 1 = r
518        let i = var(0, s32());
519        let r = var(1, s32());
520        let inc = Stmt::Assign(0, bin(BinOp::Add, i.clone(), k(s32(), 1), s32()));
521        let f = Func {
522            name: "dw".into(),
523            slots: vec![s32(), s32()],
524            n_params: 0,
525            ret: 1,
526            body: vec![Stmt::Loop {
527                cond: Some(bin(BinOp::Lt, i.clone(), k(s32(), 100), Ty::BIT)),
528                body: vec![
529                    inc,
530                    Stmt::If(
531                        bin(BinOp::Eq, i.clone(), k(s32(), 2), Ty::BIT),
532                        vec![Stmt::Continue],
533                        Vec::new(),
534                    ),
535                    Stmt::If(
536                        bin(BinOp::Eq, i.clone(), k(s32(), 5), Ty::BIT),
537                        vec![Stmt::Break],
538                        Vec::new(),
539                    ),
540                    Stmt::Assign(1, bin(BinOp::Add, r.clone(), i.clone(), s32())),
541                ],
542                step: Vec::new(),
543                test_first: false,
544            }],
545        };
546        // i = 1 (r = 1), 2 (skipped), 3 (r = 4), 4 (r = 8), 5 (break).
547        assert_eq!(call(&[f], 0, &[], &[]).unwrap(), n(8));
548    }
549
550    #[test]
551    fn a_function_reads_state_and_an_unreadable_state_is_an_error() {
552        // f(a) = a + state0
553        let f = Func {
554            name: "f".into(),
555            slots: vec![s32(), s32()],
556            n_params: 1,
557            ret: 1,
558            body: vec![Stmt::Assign(
559                1,
560                bin(BinOp::Add, var(0, s32()), Expr::State(0, s32()), s32()),
561            )],
562        };
563        assert_eq!(
564            call(std::slice::from_ref(&f), 0, &[n(2)], &[Some(n(40))]).unwrap(),
565            n(42)
566        );
567        assert_eq!(
568            call(&[f], 0, &[n(2)], &[None]),
569            Err(FuncError::Eval(ConstraintEvalError::StateUnknown(0)))
570        );
571    }
572
573    #[test]
574    fn division_by_zero_inside_a_function_is_an_error() {
575        let f = Func {
576            name: "d".into(),
577            slots: vec![s32(), s32()],
578            n_params: 1,
579            ret: 1,
580            body: vec![Stmt::Assign(
581                1,
582                bin(BinOp::Div, k(s32(), 1), var(0, s32()), s32()),
583            )],
584        };
585        assert_eq!(
586            call(&[f], 0, &[n(0)], &[]),
587            Err(FuncError::Eval(ConstraintEvalError::DivideByZero))
588        );
589    }
590
591    #[test]
592    fn only_calls_with_fixed_arguments_are_folded() {
593        let f = [count_ones()];
594        let ground = Expr::Array(ArrayNode::Call {
595            func: 0,
596            args: vec![k(u(10), 0b111)],
597            ty: s32(),
598        });
599        let open = Expr::Array(ArrayNode::Call {
600            func: 0,
601            args: vec![var(0, u(10))],
602            ty: s32(),
603        });
604        let e = bin(BinOp::Add, ground, open.clone(), s32());
605        let folded = fold_ground_calls(&e, &f, &[]).unwrap();
606        assert_eq!(folded, bin(BinOp::Add, k(s32(), 3), open, s32()));
607        // A negation of a ground call folds under it too.
608        let neg = Expr::Unary(
609            UnOp::Neg,
610            Box::new(Expr::Array(ArrayNode::Call {
611                func: 0,
612                args: vec![k(u(10), 1)],
613                ty: s32(),
614            })),
615            s32(),
616        );
617        assert_eq!(
618            fold_ground_calls(&neg, &f, &[]).unwrap(),
619            Expr::Unary(UnOp::Neg, Box::new(k(s32(), 1)), s32())
620        );
621    }
622}
vj_sim/constraints/func.rs

vj_sim/constraints/
func.rs
