Skip to main content

CascadingShrinker

protest_extras::shrinking

Struct CascadingShrinker 

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

Cascading shrinker that applies multiple shrinking strategies in sequence

This strategy tries multiple shrinking approaches and combines their results, allowing for more thorough exploration of the shrink space.

§Examples

use protest_extras::shrinking::CascadingShrinker;

let value = vec![10, 20, 30, 40, 50];

// Try removing elements, then halving, then targeted shrinking
let shrinker = CascadingShrinker::new(value);
let shrunk: Vec<_> = shrinker.shrink().take(20).collect();

// Will explore many different shrinking paths
assert!(!shrunk.is_empty());

Implementations§

Source§

impl<T: Clone> CascadingShrinker<T>

Source

pub fn new(value: T) -> Self

Create a new cascading shrinker

Examples found in repository?
examples/advanced_shrinking.rs (line 41)
33fn example_1_cascading_shrinker() {
34    println!("Example 1: CascadingShrinker - Thorough Exploration");
35    println!("{}", "-".repeat(60));
36
37    let original = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
38    println!("Original vector: {:?}", original);
39    println!("Length: {}", original.len());
40
41    let shrinker = CascadingShrinker::new(original.clone());
42    let candidates: Vec<_> = shrinker.shrink().collect();
43
44    println!(
45        "\nCascading shrinking generates {} candidates:",
46        candidates.len()
47    );
48    println!("  - Single element removals: {}", original.len());
49    println!("  - Chunk removals (halves, thirds): ~6");
50    println!("  - Empty vector: 1");
51    println!(
52        "  - Adjacent pair removals: {}",
53        original.len().saturating_sub(1)
54    );
55
56    // Show some interesting candidates
57    println!("\nSample candidates:");
58    for (i, candidate) in candidates.iter().take(5).enumerate() {
59        println!("  {}: {:?} (len={})", i + 1, candidate, candidate.len());
60    }
61
62    // The cascading shrinker is useful when you want to explore many
63    // different ways to shrink a value without knowing which will be most effective
64    println!("\nUse Case:");
65    println!("  Best for: Exploring all shrinking possibilities systematically");
66    println!("  When to use: When you don't know what minimal form looks like");
67}
68
69/// Example 2: GuidedShrinker with test feedback
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 value(&self) -> &T

Get the original value

Source§

impl<T: Clone + Debug + 'static> CascadingShrinker<Vec<T>>

Source

pub fn shrink(&self) -> Box<dyn Iterator<Item = Vec<T>>>

Shrink using multiple strategies

Examples found in repository?
examples/advanced_shrinking.rs (line 42)
33fn example_1_cascading_shrinker() {
34    println!("Example 1: CascadingShrinker - Thorough Exploration");
35    println!("{}", "-".repeat(60));
36
37    let original = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
38    println!("Original vector: {:?}", original);
39    println!("Length: {}", original.len());
40
41    let shrinker = CascadingShrinker::new(original.clone());
42    let candidates: Vec<_> = shrinker.shrink().collect();
43
44    println!(
45        "\nCascading shrinking generates {} candidates:",
46        candidates.len()
47    );
48    println!("  - Single element removals: {}", original.len());
49    println!("  - Chunk removals (halves, thirds): ~6");
50    println!("  - Empty vector: 1");
51    println!(
52        "  - Adjacent pair removals: {}",
53        original.len().saturating_sub(1)
54    );
55
56    // Show some interesting candidates
57    println!("\nSample candidates:");
58    for (i, candidate) in candidates.iter().take(5).enumerate() {
59        println!("  {}: {:?} (len={})", i + 1, candidate, candidate.len());
60    }
61
62    // The cascading shrinker is useful when you want to explore many
63    // different ways to shrink a value without knowing which will be most effective
64    println!("\nUse Case:");
65    println!("  Best for: Exploring all shrinking possibilities systematically");
66    println!("  When to use: When you don't know what minimal form looks like");
67}
68
69/// Example 2: GuidedShrinker with test feedback
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§

impl CascadingShrinker<i32>

Source

pub fn shrink(&self) -> Box<dyn Iterator<Item = i32>>

Shrink using multiple strategies for integers

Trait Implementations§

Source§

impl<T: Clone> Clone for CascadingShrinker<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 CascadingShrinker<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 CascadingShrinker<T>
where T: Freeze,

§

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

§

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

§

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

§

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

§

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

§

impl<T> UnwindSafe for CascadingShrinker<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