strop/
bruteforce.rs

1use crate::test;
2use crate::test::Vals;
3use crate::BruteforceSearch;
4use crate::Callable;
5
6/// Performs a brute force search over a given search space `Searchable`
7#[derive(Debug, Clone)]
8pub struct BruteForce<
9    Insn,
10    InputParameters,
11    ReturnValue: Clone,
12    TargetFunction: Callable<InputParameters, ReturnValue>,
13    Searchable: Callable<InputParameters, ReturnValue> + BruteforceSearch<Insn>,
14> {
15    target_function: TargetFunction,
16    candidate: Searchable,
17    tests: Vec<(InputParameters, ReturnValue)>,
18    input: std::marker::PhantomData<InputParameters>,
19    ret: std::marker::PhantomData<ReturnValue>,
20    insn: std::marker::PhantomData<Insn>,
21
22    /// Keeps track of how many iterations the bruteforce search has been through.
23    pub count: usize,
24}
25
26/// Converts something to a BruteForce, which performs brute force searches over some search space
27/// for a given function.
28pub trait ToBruteForce<
29    Insn,
30    InputParameters,
31    ReturnValue: Clone,
32    TargetFunction: Callable<InputParameters, ReturnValue>,
33>
34{
35    /// Return a BruteForce
36    fn to_bruteforce(
37        self,
38        target_function: TargetFunction,
39    ) -> BruteForce<Insn, InputParameters, ReturnValue, TargetFunction, Self>
40    where
41        Self: Callable<InputParameters, ReturnValue> + BruteforceSearch<Insn> + Sized;
42}
43
44impl<
45        Insn,
46        T: Callable<InputParameters, ReturnValue> + BruteforceSearch<Insn> + Clone,
47        InputParameters,
48        ReturnValue: Clone + Vals,
49        TargetFunction: Callable<InputParameters, ReturnValue>,
50    > ToBruteForce<Insn, InputParameters, ReturnValue, TargetFunction> for T
51where
52    Self: Callable<InputParameters, ReturnValue>,
53    InputParameters: test::Vals,
54{
55    fn to_bruteforce(
56        self,
57        target_function: TargetFunction,
58    ) -> BruteForce<Insn, InputParameters, ReturnValue, TargetFunction, Self> {
59        BruteForce::new(target_function, self)
60    }
61}
62
63impl<
64        Insn,
65        InputParameters: Copy + Vals,
66        ReturnValue: Vals + std::cmp::PartialEq + Clone,
67        TargetFunction: Callable<InputParameters, ReturnValue>,
68        Searchable: Callable<InputParameters, ReturnValue> + crate::BruteforceSearch<Insn> + Clone,
69    > BruteForce<Insn, InputParameters, ReturnValue, TargetFunction, Searchable>
70{
71    /// Constructs a new `BruteForce`
72    pub fn new(target_function: TargetFunction, initial_candidate: Searchable) -> Self {
73        let candidate = initial_candidate;
74        let tests = test::quick_tests(&target_function);
75        Self {
76            target_function,
77            candidate,
78            tests,
79            input: std::marker::PhantomData,
80            insn: std::marker::PhantomData,
81            ret: std::marker::PhantomData,
82            count: 0,
83        }
84    }
85
86    /// Returns the candidate currently under consideration
87    pub fn candidate(&self) -> &Searchable {
88        &self.candidate
89    }
90
91    /// Advances the candidate to the next position in the search space
92    pub fn step(&mut self) -> crate::IterationResult {
93        self.count += 1;
94        self.candidate.step();
95        Ok(())
96    }
97
98    /// Tests that the candidate matches the target function
99    pub fn test(&mut self) -> bool {
100        match test::passes(&self.candidate, &self.tests) {
101            Err(_) => {
102                // The candidate does not pass the test case(s)
103                false
104            }
105            Ok(false) => {
106                // The candidate does not pass the test case(s)
107                false
108            }
109            Ok(true) => {
110                // Found a candidate which passes all known test cases.
111                // Let's fuzz test the candidate
112                if let Some(test_case) = test::fuzz(&self.target_function, &self.candidate, 5000) {
113                    // We've fuzzed the functions against eachother and found another test case.
114                    // So keep hold of this new test case
115                    self.tests.push(test_case);
116                    false
117                } else {
118                    // The candidate passed all known test cases and also a fuzz test, so let's say
119                    // it's good enough and return it
120                    true
121                }
122            }
123        }
124    }
125
126    /// Returns the next function that matches the target function
127    pub fn search(&mut self) -> Option<Searchable> {
128        loop {
129            self.step().ok()?;
130            if self.test() {
131                return Some(self.candidate.clone());
132            }
133        }
134    }
135}
strop/bruteforce.rs

strop/
bruteforce.rs
