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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
//! Index-based shrink passes: `lower_and_bump` and `try_shortening_via_increment`.
//!
//! Both passes use the `to_index`/`from_index` API on `ChoiceKind` for
//! type-generic shrinking.
use std::collections::HashMap;
use crate::native::bignum::{BigInt, BigUint, Zero};
use crate::native::core::{ChoiceKind, ChoiceValue};
use super::{ShrinkResult, Shrinker};
fn is_sequence(kind: &std::sync::Arc<ChoiceKind>) -> bool {
matches!(**kind, ChoiceKind::Bytes(_) | ChoiceKind::String(_))
}
impl<'a> Shrinker<'a> {
/// For each indexed node not at simplest, try decrementing it (lowering
/// the index) and bumping a later node (raising its index).
///
/// Value punning (via `with_value` + `for_choices` with `prefix_nodes`)
/// handles the case where decrementing changes the kind at position
/// `j` (e.g. a `one_of` branch switch).
pub(super) fn lower_and_bump(&mut self) -> ShrinkResult<()> {
let max_gap = std::cmp::min(self.current_nodes.len(), 4);
for gap in 1..max_gap {
let mut idx = 0;
while idx < self.current_nodes.len() {
let i = idx;
let node_i = self.current_nodes[i].clone();
let kind_i = node_i.kind.clone();
if is_sequence(&kind_i) {
idx += 1;
continue;
}
let current_idx = kind_i.to_index(&node_i.value);
if current_idx.is_zero() {
idx += 1;
continue;
}
// Decrement targets: simplest (index 0), then `current-1`.
// Trying simplest first handles cases where intermediate steps
// don't produce interesting results but the full decrement
// does (e.g. sampled_from where only index 0 satisfies a
// downstream constraint).
let mut decrement_targets: Vec<ChoiceValue> = Vec::new();
if current_idx > BigUint::from(1u32) {
let v0 = kind_i
.from_index(BigUint::zero())
.expect("from_index(0) is simplest and always valid");
decrement_targets.push(v0);
}
// `from_index(current_idx - 1)` can be None for bounded float
// ranges with gaps.
if let Some(v_prev) = kind_i.from_index(¤t_idx - BigUint::from(1u32)) {
if !decrement_targets.contains(&v_prev) {
decrement_targets.push(v_prev);
}
}
// Find bump target `j`: the gap'th node after i. Use
// `checked_add` proper so that an index near `usize::MAX`
// doesn't silently wrap in release builds; the trailing
// `filter` then bounds-checks against the node-list length.
let j_opt = i.checked_add(gap).filter(|&j| j < self.current_nodes.len());
let Some(j) = j_opt else {
idx += 1;
continue;
};
for new_val in &decrement_targets {
// Build the decrement attempt and run it. Running both
// `attempt` and the zero-padded variant is for the
// side-effect on `current` (the shrinker auto-updates
// to smaller interesting results).
let mut attempt = self.current_nodes.clone();
attempt[i] = attempt[i].with_value(new_val.clone());
self.consider(&attempt)?;
let mut zeroed = attempt.clone();
for node in &mut zeroed[i + 1..] {
let s = node.kind.simplest();
*node = node.with_value(s);
}
self.consider(&zeroed)?;
// Try bumping node `j` at relative and absolute index
// offsets — replace-with-validate skips when the
// bumped value doesn't fit the *current* kind at j
// (which may have shifted under punning between
// iterations).
if j < self.current_nodes.len() && !is_sequence(&self.current_nodes[j].kind) {
let kind_j = self.current_nodes[j].kind.clone();
let target_idx = kind_j.to_index(&self.current_nodes[j].value);
let mut bumped_any_relative = false;
for bump in [1u32, 2, 4] {
let candidate_idx = &target_idx + BigUint::from(bump);
if let Some(bumped) = kind_j.from_index(candidate_idx) {
if try_bump_ij(self, i, new_val, j, &bumped)? {
bumped_any_relative = true;
break;
}
}
}
if !bumped_any_relative {
let max_j = kind_j.max_index();
let mut p = BigUint::from(1u32);
for _ in 0..8 {
if p > max_j {
break;
}
let p_minus_one = &p - BigUint::from(1u32);
if let Some(v) = kind_j.from_index(p_minus_one) {
try_bump_ij(self, i, new_val, j, &v)?;
}
if let Some(v) = kind_j.from_index(p.clone()) {
try_bump_ij(self, i, new_val, j, &v)?;
}
p *= BigUint::from(2u32);
}
}
}
}
idx += 1;
}
}
Ok(())
}
/// For each indexed node, try *incrementing* its index to see if the test
/// takes a shorter path (e.g. triggering an earlier exit).
///
/// A value shrinker can only make values simpler; sometimes making a
/// value *less* simple (e.g. `false → true`) causes an earlier exit,
/// producing a shorter and thus overall simpler choice sequence.
pub(super) fn try_shortening_via_increment(&mut self) -> ShrinkResult<()> {
let mut i = 0;
while i < self.current_nodes.len() {
let node = self.current_nodes[i].clone();
let kind = node.kind.clone();
if is_sequence(&kind) {
i += 1;
continue;
}
let current_idx = kind.to_index(&node.value);
let mut candidates: Vec<ChoiceValue> = Vec::new();
for d in [1u32, 2, 4, 8, 16] {
let t = ¤t_idx + BigUint::from(d);
if let Some(v) = kind.from_index(t) {
if v != node.value && !candidates.contains(&v) {
candidates.push(v);
}
}
}
if let Some(v) = kind.from_index(kind.max_index()) {
if v != node.value && !candidates.contains(&v) {
candidates.push(v);
}
}
// Also try powers of 2 (and negatives) as raw values. This covers
// large index-space jumps that exponential index probing misses.
if let ChoiceKind::Integer(ic) = kind.as_ref() {
for e in 0u32..11 {
let magnitude = BigInt::from(1u64 << e);
for sign in [BigInt::from(1), BigInt::from(-1)] {
let Some(av) = ic.value_from_bigint(&(sign * &magnitude)) else {
continue;
};
let candidate_val = ChoiceValue::Integer(av);
if kind.validate(&candidate_val)
&& candidate_val != node.value
&& !candidates.contains(&candidate_val)
{
candidates.push(candidate_val);
}
}
}
}
if candidates.is_empty() {
i += 1;
continue;
}
for incremented in &candidates {
if i >= self.current_nodes.len() {
break;
}
let mut attempt = self.current_nodes.clone();
attempt[i] = attempt[i].with_value(incremented.clone());
let mut zeroed = attempt.clone();
for node in &mut zeroed[i + 1..] {
let s = node.kind.simplest();
*node = node.with_value(s);
}
self.consider(&zeroed)?;
}
i += 1;
}
Ok(())
}
}
/// Helper for `lower_and_bump`: replace `{i: new_val, j: bump_val}` if the
/// kind at j validates `bump_val`. Returns whether the attempt was
/// interesting.
pub(super) fn try_bump_ij(
shrinker: &mut Shrinker<'_>,
i: usize,
new_val: &ChoiceValue,
j: usize,
bump_val: &ChoiceValue,
) -> ShrinkResult<bool> {
// `replace` checks `j < len` (via its `i >= attempt.len()`
// short-circuit) and `kind.validate(bump_val)` itself, so the
// pre-checks here would be redundant. Let `replace` reject
// invalid attempts on its own.
let replacements: HashMap<usize, ChoiceValue> = [(i, new_val.clone()), (j, bump_val.clone())]
.into_iter()
.collect();
shrinker.replace(&replacements)
}