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
// Sequence-ordering shrink passes: sort_values, swap_adjacent_blocks.
use std::collections::HashMap;
use crate::native::core::{ChoiceKind, ChoiceValue};
use super::{ShrinkResult, Shrinker};
impl<'a> Shrinker<'a> {
/// Try sorting groups of same-type choices by sort key.
///
/// 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) -> ShrinkResult<()> {
// 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) -> ShrinkResult<()> {
self.try_sort_group(|k| matches!(k, ChoiceKind::Integer(_)))
}
pub(super) fn sort_values_booleans(&mut self) -> ShrinkResult<()> {
self.try_sort_group(|k| matches!(k, ChoiceKind::Boolean(_)))
}
fn try_sort_group<F>(&mut self, matches_kind: F) -> ShrinkResult<()>
where
F: Fn(&ChoiceKind) -> bool,
{
let indices: Vec<usize> = self
.current_nodes
.iter()
.enumerate()
.filter_map(|(i, n)| {
if matches_kind(n.kind.as_ref()) {
Some(i)
} else {
None
}
})
.collect();
if indices.len() < 2 {
return Ok(());
}
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 Ok(());
}
}
// Insertion-sort fallback. 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.as_ref())
})
.collect();
if j >= valid.len() {
break;
}
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;
}
}
Ok(())
}
/// 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) -> ShrinkResult<()> {
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.as_ref()))
.collect();
let types_b: Vec<std::mem::Discriminant<ChoiceKind>> = (0..block_size)
.map(|k| std::mem::discriminant(self.current_nodes[j + k].kind.as_ref()))
.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;
}
}
Ok(())
}
}
#[cfg(test)]
#[path = "../../../tests/embedded/native/shrinker_sequence_tests.rs"]
mod tests;