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
// Sequence-ordering shrink passes: sort_values, swap_adjacent_blocks.
use std::collections::HashMap;
use crate::native::core::{ChoiceKind, ChoiceValue};
use super::Shrinker;
impl<'a> Shrinker<'a> {
/// Try sorting groups of same-type choices by sort key.
///
/// Port of Hypothesis's `sort_values`. Groups choices by type and tries
/// sorting each group so simpler values come first, enabling other
/// passes to further reduce the leading choices. First attempts a
/// full sort; if that fails the `consider` predicate, falls back to
/// an insertion-sort loop where each adjacent swap is validated
/// individually. The fallback matters when earlier swaps cause
/// structural changes (e.g. value punning on collection-bearing
/// kinds) that would make the full sort's replace unreachable.
pub(super) fn sort_values(&mut self) {
// Sort integer choices by absolute value.
self.sort_values_integers();
// Sort boolean choices: false (0) before true (1).
self.sort_values_booleans();
}
pub(super) fn sort_values_integers(&mut self) {
self.try_sort_group(|k| matches!(k, ChoiceKind::Integer(_)));
}
pub(super) fn sort_values_booleans(&mut self) {
self.try_sort_group(|k| matches!(k, ChoiceKind::Boolean(_)));
}
fn try_sort_group<F>(&mut self, matches_kind: F)
where
F: Fn(&ChoiceKind) -> bool,
{
let indices: Vec<usize> = self
.current_nodes
.iter()
.enumerate()
.filter_map(|(i, n)| if matches_kind(&n.kind) { Some(i) } else { None })
.collect();
if indices.len() < 2 {
return;
}
let values: Vec<ChoiceValue> = indices
.iter()
.map(|&i| self.current_nodes[i].value.clone())
.collect();
let mut keyed: Vec<_> = indices
.iter()
.map(|&i| {
(
self.current_nodes[i].sort_key(),
self.current_nodes[i].value.clone(),
)
})
.collect();
keyed.sort_by(|a, b| a.0.cmp(&b.0));
let sorted_values: Vec<ChoiceValue> = keyed.into_iter().map(|(_, v)| v).collect();
if sorted_values != values {
let replacements: HashMap<usize, ChoiceValue> = indices
.iter()
.zip(sorted_values.iter())
.map(|(&i, v)| (i, v.clone()))
.collect();
if self.replace(&replacements) {
return;
}
}
// Insertion-sort fallback (Hypothesis's `feature_enabled("collections")`
// branch of `_try_sort_group`). Each iteration refreshes the valid
// indices because a prior successful swap can shorten current_nodes
// or change kinds at fixed positions via value punning.
for pos in 1..indices.len() {
let mut j = pos;
while j > 0 {
let valid: Vec<usize> = indices
.iter()
.copied()
.filter(|&i| {
i < self.current_nodes.len() && matches_kind(&self.current_nodes[i].kind)
})
.collect();
if j >= valid.len() {
break; // nocov — only reached after a concurrent shrink shortened `valid`
}
let idx_j = valid[j];
let idx_prev = valid[j - 1];
if self.current_nodes[idx_prev].sort_key() <= self.current_nodes[idx_j].sort_key() {
break;
}
let v_j = self.current_nodes[idx_j].value.clone();
let v_prev = self.current_nodes[idx_prev].value.clone();
let mut swap = HashMap::new();
swap.insert(idx_prev, v_j);
swap.insert(idx_j, v_prev);
if self.replace(&swap) {
j -= 1;
continue;
}
break;
}
}
}
/// Port of Hypothesis's `swap_adjacent_blocks`.
///
/// For each block size 2..=8, tries swapping adjacent blocks of the same
/// type structure (same sequence of choice kinds). This handles cases like
/// list entries where each entry spans multiple choices (e.g. [continue,
/// value]) and the sorting pass can't swap individual values without
/// breaking structure.
pub(super) fn swap_adjacent_blocks(&mut self) {
for block_size in 2usize..=8 {
let mut i = 0;
while i + 2 * block_size <= self.current_nodes.len() {
let j = i + block_size;
// Check that both blocks have matching type structure.
let types_a: Vec<std::mem::Discriminant<ChoiceKind>> = (0..block_size)
.map(|k| std::mem::discriminant(&self.current_nodes[i + k].kind))
.collect();
let types_b: Vec<std::mem::Discriminant<ChoiceKind>> = (0..block_size)
.map(|k| std::mem::discriminant(&self.current_nodes[j + k].kind))
.collect();
if types_a != types_b {
i += 1;
continue;
}
let block_a: Vec<ChoiceValue> = (0..block_size)
.map(|k| self.current_nodes[i + k].value.clone())
.collect();
let block_b: Vec<ChoiceValue> = (0..block_size)
.map(|k| self.current_nodes[j + k].value.clone())
.collect();
if block_a == block_b {
i += 1;
continue;
}
// Try swapping block_a and block_b.
let mut swap = HashMap::new();
for k in 0..block_size {
swap.insert(i + k, block_b[k].clone());
swap.insert(j + k, block_a[k].clone());
}
self.replace(&swap);
i += 1;
}
}
}
}