patronus 0.37.0

Hardware bug-finding toolkit.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

// Copyright 2024 Cornell University
// released under BSD 3-Clause License
// author: Kevin Laeufer <laeufer@cornell.edu>

//! # Expression Traversals
//!
//! Contains functions to simplify non-recursive implementations of expression traversals.

use crate::expr::{Context, Expr, ExprRef, ForEachChild};

/// Visits expression nodes bottom up while propagating values
#[inline]
pub fn bottom_up<R>(
    ctx: &Context,
    expr: ExprRef,
    f: impl FnMut(&Context, ExprRef, &[R]) -> R,
) -> R {
    bottom_up_multi_pat(
        ctx,
        expr,
        |_ctx, expr, children| expr.for_each_child(|c| children.push(*c)),
        f,
    )
}

/// Visits expression nodes bottom up while propagating values and mutating the context.
#[inline]
pub fn bottom_up_mut<R>(
    ctx: &mut Context,
    expr: ExprRef,
    f: impl FnMut(&mut Context, ExprRef, &[R]) -> R,
) -> R {
    bottom_up_multi_pat_mut(
        ctx,
        expr,
        |_ctx, expr, children| expr.for_each_child(|c| children.push(*c)),
        f,
    )
}

/// Visits expression nodes bottom up while propagating values.
/// Can match patterns with multiple nodes that will turn into a single output value.
#[inline]
pub fn bottom_up_multi_pat<R>(
    ctx: &Context,
    expr: ExprRef,
    mut get_children: impl FnMut(&Context, &Expr, &mut Vec<ExprRef>),
    mut f: impl FnMut(&Context, ExprRef, &[R]) -> R,
) -> R {
    let mut todo = vec![(expr, false)];
    let mut stack = Vec::with_capacity(4);
    let mut child_vec = Vec::with_capacity(4);

    while let Some((e, bottom_up)) = todo.pop() {
        let expr = &ctx[e];

        // Check if there are children that we need to compute first.
        if !bottom_up {
            // check if there are child expressions to evaluate
            debug_assert!(child_vec.is_empty());
            get_children(ctx, expr, &mut child_vec);
            if !child_vec.is_empty() {
                todo.push((e, true));
                for c in child_vec.drain(..).rev() {
                    todo.push((c, false));
                }
                continue;
            }
        }

        // Otherwise, all arguments are available on the stack for us to use.
        let num_children = expr.num_children();
        let values = &stack[stack.len() - num_children..];
        let result = f(ctx, e, values);
        stack.truncate(stack.len() - num_children);
        stack.push(result);
    }

    debug_assert_eq!(stack.len(), 1);
    stack.pop().unwrap()
}

/// Visits expression nodes bottom up while propagating values and mutating the context.
/// Can match patterns with multiple nodes that will turn into a single output value.
#[inline]
pub fn bottom_up_multi_pat_mut<R>(
    ctx: &mut Context,
    expr: ExprRef,
    mut get_children: impl FnMut(&Context, &Expr, &mut Vec<ExprRef>),
    mut f: impl FnMut(&mut Context, ExprRef, &[R]) -> R,
) -> R {
    let mut todo = vec![(expr, false)];
    let mut stack = Vec::with_capacity(4);
    let mut child_vec = Vec::with_capacity(4);

    while let Some((e, bottom_up)) = todo.pop() {
        let expr = &ctx[e];

        // Check if there are children that we need to compute first.
        if !bottom_up {
            // check if there are child expressions to evaluate
            debug_assert!(child_vec.is_empty());
            get_children(ctx, expr, &mut child_vec);
            if !child_vec.is_empty() {
                todo.push((e, true));
                for c in child_vec.drain(..).rev() {
                    todo.push((c, false));
                }
                continue;
            }
        }

        // Otherwise, all arguments are available on the stack for us to use.
        let num_children = expr.num_children();
        let values = &stack[stack.len() - num_children..];
        let result = f(ctx, e, values);
        stack.truncate(stack.len() - num_children);
        stack.push(result);
    }

    debug_assert_eq!(stack.len(), 1);
    stack.pop().unwrap()
}

#[derive(Debug, Copy, Clone, Eq, PartialEq)]
pub enum TraversalCmd {
    Stop,
    Continue,
}

/// Visits expression from top to bottom. Halts exploration if a false is returned.
#[inline]
pub fn top_down(
    ctx: &Context,
    expr: ExprRef,
    mut f: impl FnMut(&Context, ExprRef) -> TraversalCmd,
) {
    let mut todo = vec![expr];
    while let Some(e) = todo.pop() {
        let do_continue = f(ctx, e) == TraversalCmd::Continue;
        if do_continue {
            ctx[e].for_each_child(|&c| todo.push(c));
        }
    }
}