advanced_shrinking/
advanced_shrinking.rs

1//! Advanced Shrinking Strategies Example
2//!
3//! This example demonstrates the three advanced shrinking strategies in protest-extras:
4//! 1. CascadingShrinker - Applies multiple strategies in sequence
5//! 2. GuidedShrinker - Uses test feedback to guide minimization
6//! 3. ConfigurableShrinker - Supports breadth-first and depth-first search
7//!
8//! Run with: cargo run --example advanced_shrinking
9
10use protest_extras::shrinking::{
11    CascadingShrinker, ConfigurableShrinker, GuidedShrinker, ShrinkStrategy,
12};
13
14fn main() {
15    println!("=== Advanced Shrinking Strategies Demo ===\n");
16
17    example_1_cascading_shrinker();
18    println!("\n{}\n", "=".repeat(60));
19
20    example_2_guided_shrinker();
21    println!("\n{}\n", "=".repeat(60));
22
23    example_3_configurable_shrinker_dfs();
24    println!("\n{}\n", "=".repeat(60));
25
26    example_4_configurable_shrinker_bfs();
27    println!("\n{}\n", "=".repeat(60));
28
29    example_5_comparing_strategies();
30}
31
32/// Example 1: CascadingShrinker for thorough exploration
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}
advanced_shrinking/advanced_shrinking.rs

advanced_shrinking/
advanced_shrinking.rs
