vj_sim/constraints/

walk.rs

//! The object traversals behind `pre_randomize()` / `post_randomize()` (Task
//! C18; IEEE 1800-2023 18.6.2).
//!
//! "Every class contains pre_randomize() and post_randomize() methods, which
//! are automatically called by randomize() before and after computing new
//! random values." And, for object members: "If the class is [a] random
//! object member of another class ... pre_randomize() and post_randomize()
//! are called on the object and on each of its enabled `rand` object
//! members" (18.5.8 gives the active set; this is the same set
//! [`joint::closure`](super::joint::closure) solves).
//!
//! The hooks are compiled subroutines, which this crate cannot call, so a
//! `randomize()` call site drives the traversal itself: [`begin`] opens a walk
//! over the objects rooted at the receiver, [`next`] hands back the next
//! object whose hook the call site runs (it dispatches on the object's
//! dynamic class), and [`end`] closes it.
//!
//! * [`Phase::Pre`] is lazy pre-order: an object's `rand` members are
//!   discovered only after its own `pre_randomize()` ran, so a hook that turns
//!   a member off with `rand_mode(0)` (or replaces the member) is honoured, as
//!   it would be for the solve that follows.
//! * [`Phase::Post`] is a post-order snapshot taken after a successful solve:
//!   members before their container. The LRM leaves the sibling order
//!   unspecified; here it is the declaration order of the `rand` handles.
//!
//! An object graph may be cyclic (a doubly linked list), so every object is
//! visited exactly once.

use std::collections::{HashMap, HashSet};
use std::sync::{Mutex, OnceLock};

use super::joint::read_handle;
use super::registry::{owner, program};
use crate::objects;

/// Which hook a walk visits objects for.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Phase {
    /// `pre_randomize()`: container before members.
    Pre,
    /// `post_randomize()`: members before container.
    Post,
}

impl Phase {
    /// The phase of ABI code `code` (`0` = pre, `1` = post).
    pub fn from_code(code: u64) -> Option<Self> {
        match code {
            0 => Some(Phase::Pre),
            1 => Some(Phase::Post),
            _ => None,
        }
    }

    pub fn code(self) -> u64 {
        match self {
            Phase::Pre => 0,
            Phase::Post => 1,
        }
    }
}

struct Walk {
    /// Pre-order: objects still to visit, the next one last.
    stack: Vec<u64>,
    /// Pre-order: the object last handed out, whose members are discovered on
    /// the following [`next`].
    last: Option<u64>,
    visited: HashSet<u64>,
    /// Post-order: the remaining snapshot, the next object first.
    queue: std::collections::VecDeque<u64>,
    phase: Phase,
    statics: Vec<(u32, u64)>,
}

struct Walks {
    next_token: u64,
    open: HashMap<u64, Walk>,
}

fn walks() -> &'static Mutex<Walks> {
    static W: OnceLock<Mutex<Walks>> = OnceLock::new();
    W.get_or_init(|| {
        Mutex::new(Walks {
            next_token: 1,
            open: HashMap::new(),
        })
    })
}

/// The live objects `me` holds in its active, non-null `rand` class-handle
/// members, in declaration order. A class without a usable program has none
/// (its `randomize()` is rejected on its own).
fn members(me: u64, statics: &[(u32, u64)]) -> Vec<u64> {
    let Some(template) = objects::dynamic_template(me) else {
        return Vec::new();
    };
    let Some(entry) = program(template) else {
        return Vec::new();
    };
    let Ok(prog) = entry.as_ref() else {
        return Vec::new();
    };
    let Some(meta) = objects::rand_meta(me) else {
        return Vec::new();
    };
    let mut out = Vec::new();
    for ph in &prog.rand_handles {
        let active = match ph.prop_index {
            Some(i) => meta.rand_mode.get(i).copied().unwrap_or(true),
            None => true,
        };
        if !active {
            continue;
        }
        let Ok(o) = owner(ph.home, me, statics) else {
            continue;
        };
        if let Ok(Some(child)) = read_handle(o, ph.slot, ph.bit)
            && objects::dynamic_template(child).is_some()
        {
            out.push(child);
        }
    }
    out
}

/// The post-order of the objects reachable from `root` (iterative: an object
/// graph can be a long linked list).
fn post_order(root: u64, statics: &[(u32, u64)]) -> std::collections::VecDeque<u64> {
    let mut out = std::collections::VecDeque::new();
    let mut visited = HashSet::new();
    visited.insert(root);
    // (object, its members, index of the next member to enter)
    let mut stack = vec![(root, members(root, statics), 0usize)];
    while let Some(top) = stack.last_mut() {
        if top.2 < top.1.len() {
            let child = top.1[top.2];
            top.2 += 1;
            if visited.insert(child) {
                stack.push((child, members(child, statics), 0));
            }
        } else {
            out.push_back(top.0);
            stack.pop();
        }
    }
    out
}

/// Opens a walk of `phase` rooted at `root`; `statics` are the call site's
/// `(id, handle)` static-property objects (as for
/// [`registry::randomize`](super::registry::randomize)). Returns the token the
/// other calls take. A dead `root` gives a walk that visits nothing.
pub fn begin(root: u64, phase: Phase, statics: &[(u32, u64)]) -> u64 {
    let live = objects::dynamic_template(root).is_some();
    let mut walk = Walk {
        stack: Vec::new(),
        last: None,
        visited: HashSet::new(),
        queue: std::collections::VecDeque::new(),
        phase,
        statics: statics.to_vec(),
    };
    if live {
        match phase {
            Phase::Pre => walk.stack.push(root),
            Phase::Post => walk.queue = post_order(root, statics),
        }
    }
    let mut w = walks().lock().unwrap_or_else(|e| e.into_inner());
    let token = w.next_token;
    w.next_token += 1;
    w.open.insert(token, walk);
    token
}

/// The next object of the walk `token` to run its hook on; `0` when the walk
/// is over (or `token` is not an open walk).
pub fn next(token: u64) -> u64 {
    let mut w = walks().lock().unwrap_or_else(|e| e.into_inner());
    let Some(walk) = w.open.get_mut(&token) else {
        return 0;
    };
    match walk.phase {
        Phase::Post => walk.queue.pop_front().unwrap_or(0),
        Phase::Pre => {
            if let Some(done) = walk.last.take() {
                // Its hook has run: now its members are known. Pushed in
                // reverse so the first-declared one is visited first.
                for child in members(done, &walk.statics).into_iter().rev() {
                    walk.stack.push(child);
                }
            }
            while let Some(h) = walk.stack.pop() {
                if objects::dynamic_template(h).is_some() && walk.visited.insert(h) {
                    walk.last = Some(h);
                    return h;
                }
            }
            0
        }
    }
}

/// Closes the walk `token` (a no-op for an unknown token).
pub fn end(token: u64) {
    walks()
        .lock()
        .unwrap_or_else(|e| e.into_inner())
        .open
        .remove(&token);
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::constraints::registry::{self, Home, ProgHandle, Program};
    use crate::netlist::ClassTemplateId;
    use crate::objects::{FieldSlot, RandKind, RandProp, alloc, register_rand_props};

    const LEFT: FieldSlot = FieldSlot {
        offset: 0,
        words: 2,
    };
    const RIGHT: FieldSlot = FieldSlot {
        offset: 2,
        words: 2,
    };

    /// A class `{ rand Node left; rand Node right; }` (rand props 0 and 1).
    fn node_class(id: u32) -> ClassTemplateId {
        let t = ClassTemplateId(id);
        register_rand_props(
            t,
            vec![
                RandProp {
                    slot: LEFT,
                    kind: RandKind::Rand,
                },
                RandProp {
                    slot: RIGHT,
                    kind: RandKind::Rand,
                },
            ],
        );
        registry::register_program(
            t,
            Ok(Program {
                rand_handles: vec![
                    ProgHandle {
                        slot: LEFT,
                        home: Home::Instance,
                        prop_index: Some(0),
                        bit: 0,
                    },
                    ProgHandle {
                        slot: RIGHT,
                        home: Home::Instance,
                        prop_index: Some(1),
                        bit: 0,
                    },
                ],
                ..Program::default()
            }),
        );
        t
    }

    fn link(parent: u64, left: u64, right: u64) {
        assert!(objects::field_set(parent, LEFT, &[left, 0]));
        assert!(objects::field_set(parent, RIGHT, &[right, 0]));
    }

    fn drain(root: u64, phase: Phase) -> Vec<u64> {
        let token = begin(root, phase, &[]);
        let mut out = Vec::new();
        loop {
            let h = next(token);
            if h == 0 {
                break;
            }
            out.push(h);
            assert!(out.len() < 100, "a walk must terminate");
        }
        end(token);
        out
    }

    /// `root(a(c, d), b)`.
    fn tree(id: u32) -> [u64; 5] {
        let t = node_class(id);
        let [root, a, b, c, d] = [(); 5].map(|()| alloc(t, 4));
        link(root, a, b);
        link(a, c, d);
        [root, a, b, c, d]
    }

    #[test]
    fn pre_order_visits_a_container_before_its_members_in_declaration_order() {
        let [root, a, b, c, d] = tree(0x7c00_0001);
        assert_eq!(drain(root, Phase::Pre), vec![root, a, c, d, b]);
    }

    #[test]
    fn post_order_visits_members_before_their_container() {
        let [root, a, b, c, d] = tree(0x7c00_0002);
        assert_eq!(drain(root, Phase::Post), vec![c, d, a, b, root]);
    }

    #[test]
    fn a_cycle_and_a_shared_member_are_visited_once() {
        let t = node_class(0x7c00_0003);
        let [p, q, r] = [(); 3].map(|()| alloc(t, 4));
        link(p, q, r);
        link(q, p, r); // back edge to p, and r reached twice
        assert_eq!(drain(p, Phase::Pre), vec![p, q, r]);
        assert_eq!(drain(p, Phase::Post), vec![r, q, p]);
    }

    #[test]
    fn a_member_turned_off_by_rand_mode_is_skipped() {
        let [root, a, b, _, _] = tree(0x7c00_0004);
        let mut meta = objects::rand_meta(root).expect("meta");
        meta.rand_mode[0] = false; // `left` off
        objects::set_rand_meta(root, meta);
        assert_eq!(drain(root, Phase::Pre), vec![root, b]);
        assert_eq!(drain(root, Phase::Post), vec![b, root]);
        // `a` itself is still a perfectly good root
        assert_eq!(drain(a, Phase::Pre).len(), 3);
    }

    #[test]
    fn pre_order_sees_a_member_change_made_by_the_container_hook() {
        // The container's hook runs between `next` calls: a rand_mode flip it
        // makes before the walk resumes decides which members are visited.
        let [root, a, b, c, d] = tree(0x7c00_0005);
        let token = begin(root, Phase::Pre, &[]);
        assert_eq!(next(token), root);
        let mut meta = objects::rand_meta(root).expect("meta");
        meta.rand_mode[1] = false; // the hook turns `right` off
        objects::set_rand_meta(root, meta);
        assert_eq!(next(token), a);
        assert_eq!(next(token), c);
        assert_eq!(next(token), d);
        assert_eq!(
            next(token),
            0,
            "b was switched off before it was discovered"
        );
        end(token);
        let _ = b;
    }

    #[test]
    fn null_members_and_a_dead_root_visit_nothing_extra() {
        let t = node_class(0x7c00_0006);
        let lone = alloc(t, 4);
        assert_eq!(drain(lone, Phase::Pre), vec![lone]);
        assert_eq!(drain(lone, Phase::Post), vec![lone]);
        assert_eq!(drain(0, Phase::Pre), Vec::<u64>::new());
        assert_eq!(drain(0, Phase::Post), Vec::<u64>::new());
    }

    #[test]
    fn an_unknown_token_is_over_and_end_is_idempotent() {
        assert_eq!(next(u64::MAX), 0);
        end(u64::MAX);
        let t = node_class(0x7c00_0007);
        let h = alloc(t, 4);
        let token = begin(h, Phase::Pre, &[]);
        end(token);
        assert_eq!(next(token), 0, "a closed walk yields nothing");
    }

    #[test]
    fn phase_codes_round_trip() {
        for p in [Phase::Pre, Phase::Post] {
            assert_eq!(Phase::from_code(p.code()), Some(p));
        }
        assert_eq!(Phase::from_code(2), None);
    }
}