Skip to main content

GuidedShrinker

protest_extras::shrinking

Struct GuidedShrinker 

Source 
pub struct GuidedShrinker<T> { /* private fields */ }
Expand description

Guided shrinker that uses test feedback to prioritize shrinking directions

This shrinker runs the test on shrink candidates and uses pass/fail information to guide the search toward minimal failing cases.

§Examples

use protest_extras::shrinking::GuidedShrinker;

let value = vec![1, 2, 3, 4, 5, 6, 7, 8];

// Find minimal subset that sums to > 10
let shrinker = GuidedShrinker::new(value);
let minimal = shrinker.find_minimal(|v| v.iter().sum::<i32>() > 10);

// Will find a small subset that still sums to > 10
assert!(minimal.iter().sum::<i32>() > 10);
assert!(minimal.len() < 8);

Implementations§

Source§

impl<T: Clone> GuidedShrinker<T>

Source

pub fn new(value: T) -> Self

Create a new guided shrinker with default max iterations

Examples found in repository?
examples/advanced_shrinking.rs (line 79)
70fn example_2_guided_shrinker() {
71    println!("Example 2: GuidedShrinker - Test Feedback-Driven");
72    println!("{}", "-".repeat(60));
73
74    let original = vec![10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
75    println!("Original vector: {:?}", original);
76    println!("Sum: {}", original.iter().sum::<i32>());
77
78    // Find minimal subset that still sums to > 200
79    let shrinker = GuidedShrinker::new(original.clone());
80
81    println!("\nFinding minimal subset where sum > 200...");
82    let (minimal, iterations) = shrinker.find_minimal_with_stats(|v| v.iter().sum::<i32>() > 200);
83
84    println!("Minimal vector: {:?}", minimal);
85    println!("Sum: {}", minimal.iter().sum::<i32>());
86    println!(
87        "Reduced from {} to {} elements",
88        original.len(),
89        minimal.len()
90    );
91    println!("Iterations used: {}", iterations);
92
93    // Another example: find minimal subset containing a specific element
94    let original2 = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
95    let shrinker2 = GuidedShrinker::new(original2.clone());
96
97    println!("\nFinding minimal subset containing element 7...");
98    let (minimal2, iterations2) =
99        shrinker2.find_minimal_with_stats(|v| v.contains(&7) && !v.is_empty());
100
101    println!("Minimal vector: {:?}", minimal2);
102    println!("Iterations used: {}", iterations2);
103
104    println!("\nUse Case:");
105    println!("  Best for: Efficiently finding minimal failing examples");
106    println!(
107        "  When to use: When you can run the test many times and want the smallest counterexample"
108    );
109}
110
111/// Example 3: ConfigurableShrinker with Depth-First Search
112fn example_3_configurable_shrinker_dfs() {
113    println!("Example 3: ConfigurableShrinker - Depth-First Search");
114    println!("{}", "-".repeat(60));
115
116    let original = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
117    println!("Original vector: {:?}", original);
118
119    let shrinker =
120        ConfigurableShrinker::new(original.clone(), ShrinkStrategy::DepthFirst).with_max_depth(20);
121
122    println!("\nFinding minimal subset with length >= 3 (DFS)...");
123    let minimal = shrinker.find_minimal(|v| v.len() >= 3);
124
125    println!("Minimal vector: {:?}", minimal);
126    println!("Length: {}", minimal.len());
127
128    println!("\nDepth-First Strategy:");
129    println!("  - Follows the first successful shrink immediately");
130    println!("  - Goes deep before exploring alternatives");
131    println!("  - Fast but may not find the absolute minimal");
132    println!("  - Good when any reasonably small counterexample is sufficient");
133}
134
135/// Example 4: ConfigurableShrinker with Breadth-First Search
136fn example_4_configurable_shrinker_bfs() {
137    println!("Example 4: ConfigurableShrinker - Breadth-First Search");
138    println!("{}", "-".repeat(60));
139
140    let original = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
141    println!("Original vector: {:?}", original);
142
143    let shrinker = ConfigurableShrinker::new(original.clone(), ShrinkStrategy::BreadthFirst)
144        .with_max_depth(20);
145
146    println!("\nFinding minimal subset with length >= 3 (BFS)...");
147    let minimal = shrinker.find_minimal(|v| v.len() >= 3);
148
149    println!("Minimal vector: {:?}", minimal);
150    println!("Length: {}", minimal.len());
151
152    println!("\nBreadth-First Strategy:");
153    println!("  - Explores all shrinks at current depth before going deeper");
154    println!("  - More thorough exploration");
155    println!("  - Finds the truly minimal counterexample");
156    println!("  - Slower but more comprehensive");
157}
158
159/// Example 5: Comparing all strategies on the same problem
160fn example_5_comparing_strategies() {
161    println!("Example 5: Strategy Comparison");
162    println!("{}", "-".repeat(60));
163
164    // Problem: Find minimal subset where sum of squares > 500
165    let original = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
166    let sum_of_squares = |v: &Vec<i32>| v.iter().map(|x| x * x).sum::<i32>();
167
168    println!("Original vector: {:?}", original);
169    println!("Sum of squares: {}", sum_of_squares(&original));
170    println!("\nFinding minimal subset where sum of squares > 500\n");
171
172    // Strategy 1: Cascading (manual exploration)
173    let cascading = CascadingShrinker::new(original.clone());
174    let candidates: Vec<_> = cascading.shrink().collect();
175    let cascading_result = candidates
176        .iter()
177        .filter(|v| sum_of_squares(v) > 500)
178        .min_by_key(|v| v.len())
179        .cloned();
180
181    if let Some(result) = cascading_result {
182        println!("1. CascadingShrinker:");
183        println!("   Result: {:?}", result);
184        println!("   Length: {}", result.len());
185        println!("   Sum of squares: {}", sum_of_squares(&result));
186        println!("   Total candidates explored: {}", candidates.len());
187    }
188
189    // Strategy 2: Guided
190    let guided = GuidedShrinker::new(original.clone());
191    let (guided_result, guided_iterations) =
192        guided.find_minimal_with_stats(|v| sum_of_squares(v) > 500);
193
194    println!("\n2. GuidedShrinker:");
195    println!("   Result: {:?}", guided_result);
196    println!("   Length: {}", guided_result.len());
197    println!("   Sum of squares: {}", sum_of_squares(&guided_result));
198    println!("   Iterations: {}", guided_iterations);
199
200    // Strategy 3: DFS
201    let dfs =
202        ConfigurableShrinker::new(original.clone(), ShrinkStrategy::DepthFirst).with_max_depth(20);
203    let dfs_result = dfs.find_minimal(|v| sum_of_squares(v) > 500);
204
205    println!("\n3. ConfigurableShrinker (DFS):");
206    println!("   Result: {:?}", dfs_result);
207    println!("   Length: {}", dfs_result.len());
208    println!("   Sum of squares: {}", sum_of_squares(&dfs_result));
209
210    // Strategy 4: BFS
211    let bfs = ConfigurableShrinker::new(original.clone(), ShrinkStrategy::BreadthFirst)
212        .with_max_depth(20);
213    let bfs_result = bfs.find_minimal(|v| sum_of_squares(v) > 500);
214
215    println!("\n4. ConfigurableShrinker (BFS):");
216    println!("   Result: {:?}", bfs_result);
217    println!("   Length: {}", bfs_result.len());
218    println!("   Sum of squares: {}", sum_of_squares(&bfs_result));
219
220    println!("\n{}", "=".repeat(60));
221    println!("Summary:");
222    println!("  - Cascading: Generates all candidates upfront, manual filtering");
223    println!("  - Guided: Fast, iterative, good balance");
224    println!("  - DFS: Quick to find *a* minimal, may not be *the* minimal");
225    println!("  - BFS: Slowest but finds truly minimal counterexample");
226    println!("\nChoose based on:");
227    println!("  - How expensive is your test?");
228    println!("  - How minimal does the result need to be?");
229    println!("  - How much time do you have?");
230}
Source

pub fn with_max_iterations(value: T, max_iterations: usize) -> Self

Create a guided shrinker with custom max iterations

Source§

impl<T: Clone + Debug + PartialEq + 'static> GuidedShrinker<Vec<T>>

Source

pub fn find_minimal<F>(&self, test: F) -> Vec<T>
where F: Fn(&Vec<T>) -> bool,

Find minimal failing case using test feedback

The test function should return true if the test fails (i.e., we want to keep shrinking). Returns the smallest value that still fails the test.

Source

pub fn find_minimal_with_stats<F>(&self, test: F) -> (Vec<T>, usize)
where F: Fn(&Vec<T>) -> bool,

Find minimal failing case with detailed feedback

Returns both the minimal value and the number of iterations used.

Examples found in repository?
examples/advanced_shrinking.rs (line 82)
70fn example_2_guided_shrinker() {
71    println!("Example 2: GuidedShrinker - Test Feedback-Driven");
72    println!("{}", "-".repeat(60));
73
74    let original = vec![10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
75    println!("Original vector: {:?}", original);
76    println!("Sum: {}", original.iter().sum::<i32>());
77
78    // Find minimal subset that still sums to > 200
79    let shrinker = GuidedShrinker::new(original.clone());
80
81    println!("\nFinding minimal subset where sum > 200...");
82    let (minimal, iterations) = shrinker.find_minimal_with_stats(|v| v.iter().sum::<i32>() > 200);
83
84    println!("Minimal vector: {:?}", minimal);
85    println!("Sum: {}", minimal.iter().sum::<i32>());
86    println!(
87        "Reduced from {} to {} elements",
88        original.len(),
89        minimal.len()
90    );
91    println!("Iterations used: {}", iterations);
92
93    // Another example: find minimal subset containing a specific element
94    let original2 = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
95    let shrinker2 = GuidedShrinker::new(original2.clone());
96
97    println!("\nFinding minimal subset containing element 7...");
98    let (minimal2, iterations2) =
99        shrinker2.find_minimal_with_stats(|v| v.contains(&7) && !v.is_empty());
100
101    println!("Minimal vector: {:?}", minimal2);
102    println!("Iterations used: {}", iterations2);
103
104    println!("\nUse Case:");
105    println!("  Best for: Efficiently finding minimal failing examples");
106    println!(
107        "  When to use: When you can run the test many times and want the smallest counterexample"
108    );
109}
110
111/// Example 3: ConfigurableShrinker with Depth-First Search
112fn example_3_configurable_shrinker_dfs() {
113    println!("Example 3: ConfigurableShrinker - Depth-First Search");
114    println!("{}", "-".repeat(60));
115
116    let original = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
117    println!("Original vector: {:?}", original);
118
119    let shrinker =
120        ConfigurableShrinker::new(original.clone(), ShrinkStrategy::DepthFirst).with_max_depth(20);
121
122    println!("\nFinding minimal subset with length >= 3 (DFS)...");
123    let minimal = shrinker.find_minimal(|v| v.len() >= 3);
124
125    println!("Minimal vector: {:?}", minimal);
126    println!("Length: {}", minimal.len());
127
128    println!("\nDepth-First Strategy:");
129    println!("  - Follows the first successful shrink immediately");
130    println!("  - Goes deep before exploring alternatives");
131    println!("  - Fast but may not find the absolute minimal");
132    println!("  - Good when any reasonably small counterexample is sufficient");
133}
134
135/// Example 4: ConfigurableShrinker with Breadth-First Search
136fn example_4_configurable_shrinker_bfs() {
137    println!("Example 4: ConfigurableShrinker - Breadth-First Search");
138    println!("{}", "-".repeat(60));
139
140    let original = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
141    println!("Original vector: {:?}", original);
142
143    let shrinker = ConfigurableShrinker::new(original.clone(), ShrinkStrategy::BreadthFirst)
144        .with_max_depth(20);
145
146    println!("\nFinding minimal subset with length >= 3 (BFS)...");
147    let minimal = shrinker.find_minimal(|v| v.len() >= 3);
148
149    println!("Minimal vector: {:?}", minimal);
150    println!("Length: {}", minimal.len());
151
152    println!("\nBreadth-First Strategy:");
153    println!("  - Explores all shrinks at current depth before going deeper");
154    println!("  - More thorough exploration");
155    println!("  - Finds the truly minimal counterexample");
156    println!("  - Slower but more comprehensive");
157}
158
159/// Example 5: Comparing all strategies on the same problem
160fn example_5_comparing_strategies() {
161    println!("Example 5: Strategy Comparison");
162    println!("{}", "-".repeat(60));
163
164    // Problem: Find minimal subset where sum of squares > 500
165    let original = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];
166    let sum_of_squares = |v: &Vec<i32>| v.iter().map(|x| x * x).sum::<i32>();
167
168    println!("Original vector: {:?}", original);
169    println!("Sum of squares: {}", sum_of_squares(&original));
170    println!("\nFinding minimal subset where sum of squares > 500\n");
171
172    // Strategy 1: Cascading (manual exploration)
173    let cascading = CascadingShrinker::new(original.clone());
174    let candidates: Vec<_> = cascading.shrink().collect();
175    let cascading_result = candidates
176        .iter()
177        .filter(|v| sum_of_squares(v) > 500)
178        .min_by_key(|v| v.len())
179        .cloned();
180
181    if let Some(result) = cascading_result {
182        println!("1. CascadingShrinker:");
183        println!("   Result: {:?}", result);
184        println!("   Length: {}", result.len());
185        println!("   Sum of squares: {}", sum_of_squares(&result));
186        println!("   Total candidates explored: {}", candidates.len());
187    }
188
189    // Strategy 2: Guided
190    let guided = GuidedShrinker::new(original.clone());
191    let (guided_result, guided_iterations) =
192        guided.find_minimal_with_stats(|v| sum_of_squares(v) > 500);
193
194    println!("\n2. GuidedShrinker:");
195    println!("   Result: {:?}", guided_result);
196    println!("   Length: {}", guided_result.len());
197    println!("   Sum of squares: {}", sum_of_squares(&guided_result));
198    println!("   Iterations: {}", guided_iterations);
199
200    // Strategy 3: DFS
201    let dfs =
202        ConfigurableShrinker::new(original.clone(), ShrinkStrategy::DepthFirst).with_max_depth(20);
203    let dfs_result = dfs.find_minimal(|v| sum_of_squares(v) > 500);
204
205    println!("\n3. ConfigurableShrinker (DFS):");
206    println!("   Result: {:?}", dfs_result);
207    println!("   Length: {}", dfs_result.len());
208    println!("   Sum of squares: {}", sum_of_squares(&dfs_result));
209
210    // Strategy 4: BFS
211    let bfs = ConfigurableShrinker::new(original.clone(), ShrinkStrategy::BreadthFirst)
212        .with_max_depth(20);
213    let bfs_result = bfs.find_minimal(|v| sum_of_squares(v) > 500);
214
215    println!("\n4. ConfigurableShrinker (BFS):");
216    println!("   Result: {:?}", bfs_result);
217    println!("   Length: {}", bfs_result.len());
218    println!("   Sum of squares: {}", sum_of_squares(&bfs_result));
219
220    println!("\n{}", "=".repeat(60));
221    println!("Summary:");
222    println!("  - Cascading: Generates all candidates upfront, manual filtering");
223    println!("  - Guided: Fast, iterative, good balance");
224    println!("  - DFS: Quick to find *a* minimal, may not be *the* minimal");
225    println!("  - BFS: Slowest but finds truly minimal counterexample");
226    println!("\nChoose based on:");
227    println!("  - How expensive is your test?");
228    println!("  - How minimal does the result need to be?");
229    println!("  - How much time do you have?");
230}

Trait Implementations§

Source§

impl<T: Clone> Clone for GuidedShrinker<T>

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<T: Debug> Debug for GuidedShrinker<T>

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<T> Freeze for GuidedShrinker<T>
where T: Freeze,

§

impl<T> RefUnwindSafe for GuidedShrinker<T>
where T: RefUnwindSafe,

§

impl<T> Send for GuidedShrinker<T>
where T: Send,

§

impl<T> Sync for GuidedShrinker<T>
where T: Sync,

§

impl<T> Unpin for GuidedShrinker<T>
where T: Unpin,

§

impl<T> UnsafeUnpin for GuidedShrinker<T>
where T: UnsafeUnpin,

§

impl<T> UnwindSafe for GuidedShrinker<T>
where T: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> Pointable for T

Source§

const ALIGN: usize

The alignment of pointer.
Source§

type Init = T

The type for initializers.
Source§

unsafe fn init(init: <T as Pointable>::Init) -> usize

Initializes a with the given initializer. Read more
Source§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
Source§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
Source§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
Source§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

Source§

fn vzip(self) -> V