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
226
227
228
use {
crate::{
construct::{Construct, arbitrary},
reflection::{AlgebraicTypeFormer, PrecomputedTypeFormer, Type, info_by_id, type_of},
},
core::{any::type_name, cmp, fmt, iter, num::NonZero},
std::collections::BinaryHeap,
wyrand::WyRand,
};
/// A non-`Clone` wrapper around `usize`
/// to prevent accounting errors.
#[derive(Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
pub struct Size {
/// The internal size value that must not be `Clone`d.
size: usize,
}
/// One size for each field of each big type.
/// Compute sizes by measuring the spaces between bars (+ beginning & end),
/// noting that a binary heap can efficiently drain in sorted order.
#[derive(Debug, Default)]
pub struct Sizes {
/// All "bars" between "stars" except the
/// beginning and end of the range itself.
bars: BinaryHeap<cmp::Reverse<usize>>,
/// The end of the range itself,
/// unless that "bar" has already been used,
/// in which case this is `None` to halt.
end: Option<NonZero<usize>>,
/// The most recent "bar" to be popped.
/// This is initialized to zero, which
/// represents the left edge of the range itself.
prev: usize,
}
impl Size {
#[inline]
pub fn expanding() -> impl Iterator<Item = Self> {
(0_usize..).map(|squared_size| Self {
size: squared_size.isqrt(),
})
}
#[inline]
pub fn partition<T: Construct>(self, ctor_idx: NonZero<usize>, prng: &mut WyRand) -> Sizes {
self.partition_by_id(type_of::<T>(), ctor_idx, prng)
}
/// Use a stars-and-bars-like method to partition a total size
/// into sizes for each inductive type in its multiset of fields,
/// minus one for this node itself iff not a trivial wrapper.
#[inline]
fn partition_by_id(self, id: Type, ctor_idx: NonZero<usize>, prng: &mut WyRand) -> Sizes {
let info = info_by_id(id);
let PrecomputedTypeFormer::Algebraic(AlgebraicTypeFormer {
ref all_constructors,
..
}) = info.type_former
else {
return Sizes::default();
};
#[expect(
clippy::indexing_slicing,
reason = "internal invariants; violation should panic"
)]
let (_ctor_fn, ref deps) = all_constructors[ctor_idx.get() - 1];
// Count the number of inductive fields,
// regardless of whether they're trivial wrappers
// (e.g. `Box` is a trivial wrapper but `Box<...>` is still inductive):
let mut n_ind = 0;
for (&ty, count) in deps.constructor.immediate.iter() {
#[expect(
clippy::arithmetic_side_effects,
reason = "fields bounded by system hardware, defined to match the capacity of `usize`"
)]
if info_by_id(ty).vertex.is_inductive() {
n_ind += count.get();
}
}
self.partition_into(n_ind, prng, !info.trivial)
}
/// Partition this total size into `n` sizes
/// which add up to the original size,
/// optionally minus one iff `minus_one`.
/// # Panics
/// If `size` is `usize::MAX` and `!minus_one`.
#[inline]
pub fn partition_into(self, n: usize, prng: &mut WyRand, minus_one: bool) -> Sizes {
self.partition_into_opt(n, prng, minus_one)
.unwrap_or_default()
}
/// Partition this total size into `n` sizes
/// which add up to the original size,
/// optionally minus one iff `minus_one`.
/// # Panics
/// If `size` is `usize::MAX` and `!minus_one`.
#[inline]
pub fn partition_into_opt(self, n: usize, prng: &mut WyRand, minus_one: bool) -> Option<Sizes> {
let end = NonZero::new(self.size.checked_sub(usize::from(minus_one))?)?;
// We want `n` sections, so we'll use the spaces between
// the beginning, the end, and `n - 1` bars:
let n_bars = n.checked_sub(1)?;
// If this is a trivial wrapper and/or non-inductive type,
// don't account for it while tracking full AST size;
// otherwise, this AST node counts, so we should
// decrement the remaining size for the rest of the structure.
let n_inclusive = NonZero::new(
#[expect(
clippy::expect_used,
clippy::unwrap_in_result,
reason = "internal invariants; violation should panic"
)]
self.size
.checked_add(usize::from(!minus_one))
.expect("internal `pbt` error: size of `usize::MAX`"),
)?;
#[expect(
clippy::as_conversions,
clippy::cast_possible_truncation,
reason = "fine: definitely not > `u64::MAX` fields"
)]
let bars: BinaryHeap<cmp::Reverse<usize>> =
iter::repeat_with(|| cmp::Reverse(prng.rand() as usize % n_inclusive))
.take(n_bars)
.collect();
Some(Sizes {
bars,
prev: 0,
end: Some(end),
})
}
/// Whether to choose a potential leaf or loop constructor.
#[must_use]
#[inline]
pub fn should_recurse(&self, prng: &mut WyRand) -> bool {
#[expect(
clippy::as_conversions,
clippy::cast_possible_truncation,
reason = "fine: definitely not > `u64::MAX` constructors"
)]
NonZero::new(self.size).is_some_and(|size| prng.rand() as usize % size != 0)
}
#[inline]
#[must_use]
pub fn zero() -> Self {
Self { size: 0 }
}
}
impl fmt::Debug for Size {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
<usize as fmt::Debug>::fmt(&self.size, f)
}
}
impl fmt::Display for Size {
#[inline]
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
<usize as fmt::Display>::fmt(&self.size, f)
}
}
#[expect(clippy::missing_trait_methods, reason = "intentionally left default")]
impl Iterator for Sizes {
type Item = Size;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
let size = if let Some(cmp::Reverse(bar)) = self.bars.pop() {
// SAFETY: by the sorted invariant of `BinaryHeap`
let difference = unsafe { bar.unchecked_sub(self.prev) };
self.prev = bar;
difference
} else {
// SAFETY: by the sorted invariant of `BinaryHeap`
unsafe { self.end.take()?.get().unchecked_sub(self.prev) }
};
Some(Size { size })
}
}
impl Sizes {
/// Generate an arbitrary term of type `T` using the
/// size partitioned for it via `Size::partition`.
/// # Panics
/// If `T` is uninstantiable.
#[inline]
pub fn arbitrary<T: Construct>(&mut self, prng: &mut WyRand) -> T {
let ty = type_of::<T>();
let info = info_by_id(ty);
let size = if info.is_big() {
self.next().unwrap_or_default()
} else {
Size { size: 0 }
};
#[expect(clippy::todo, reason = "TODO")]
let Some(t) = arbitrary::<T>(prng, size) else {
todo!(
"uninstantiable type `{}` in `{}`",
type_name::<T>(),
type_name::<Self>(),
);
};
t
}
}
impl Drop for Sizes {
#[inline]
fn drop(&mut self) {
debug_assert_eq!(
self.next(),
None,
"internal `pbt` error: inductive type mis-count",
);
}
}