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
229
230
231
232
//! Call summaries for the staged verifier: backward dependency (which call
//! arguments stay relevant) and forward effect (what facts a call adds).
pub(crate) mod effects;
mod dependencies;
pub(crate) mod callback;
pub(crate) use dependencies::dependency_summary;
/// Dependency summary consumed by the backward visitor.
#[derive(Clone, Debug)]
pub(crate) struct CallDependencySummary {
/// If the call destination is relevant, these call arguments are relevant.
pub return_depends_on_args: Vec<usize>,
/// Arguments whose referents the callee may write.
pub write_args: Vec<usize>,
/// Arguments the backward slicer needs to model those writes.
pub write_inputs: Vec<usize>,
}
impl CallDependencySummary {
/// Conservative fallback: keep all arguments relevant.
fn fallback(arg_count: usize) -> Self {
Self {
return_depends_on_args: (0..arg_count).collect(),
write_args: Vec::new(),
write_inputs: Vec::new(),
}
}
}
/// Effect summary consumed by the forward visitor.
pub(crate) type CallEffectSummary = Vec<CallEffect>;
/// Path-local effect produced by a retained call.
#[derive(Clone, Debug)]
pub(crate) enum CallEffect {
/// The returned `MaybeUninit<T>` wrapper is valid but its inner `T` is not initialized.
ReturnUninitWrapper,
/// The return value aliases or is a direct value flow from an argument.
ReturnAliasArg { arg: usize },
/// The return value is a transparent copy of an argument's *value*
/// (`MaybeUninit::assume_init`, `ManuallyDrop::into_inner`): same term and
/// facts, retyped to the destination — no pointer `non_null` forcing.
ReturnArgValue { arg: usize },
ReturnOpaque,
ReturnSizeOfVal { arg: usize },
ReturnRawEq { left_arg: usize, right_arg: usize },
ReturnExactDiv { lhs_arg: usize, rhs_arg: usize },
/// `select_unpredictable(cond, x, y)` returns either `x` or `y`: the result
/// is one of the two candidate values (`args[1]`/`args[2]`), non-deterministic
/// since the boolean selector (`args[0]`) is unpredictable.
SelectUnpredictable,
/// The return value is a pointer extracted from an aggregate/reference arg.
ReturnPointerFromArg { arg: usize },
ReturnWrappingPointerOffset { base_arg: usize, offset_arg: usize },
ReturnPtrOffsetFrom { ptr_arg: usize, base_arg: usize },
/// The return value is known to be non-zero.
ReturnNonZero,
/// The return value is known to satisfy a concrete alignment.
ReturnAligned,
/// The return value is a concrete layout/numeric constant.
ReturnConst { value: u64 },
/// The call writes one initialized element through a pointer argument.
WriteMemory { pointer_arg: usize },
CopyMemory { source_arg: usize, destination_arg: usize, count_arg: usize },
SwapMemory { left_arg: usize, right_arg: usize },
FillBytes { pointer_arg: usize, byte_arg: usize, count_arg: usize },
/// The return value is a pointer backed by a fresh allocation of
/// `size_arg` elements × `elem_size` bytes. The base address is taken
/// from `pointer_arg`. Used for `from_raw_parts(ptr, len)`.
ReturnFreshAllocation {
pointer_arg: usize,
size_arg: usize,
elem_size: u64,
},
/// `alloc::alloc::exchange_malloc(size, align)` — a fresh allocation of
/// `size_arg` bytes, returned as `*mut u8`.
ReturnExchangeMalloc { size_arg: usize },
/// The return value is `min(lhs_arg, rhs_arg)`, satisfying
/// `return <= lhs_arg` and `return <= rhs_arg`.
ReturnMin { lhs_arg: usize, rhs_arg: usize },
/// The return value is `max(lhs_arg, rhs_arg)`.
ReturnMax { lhs_arg: usize, rhs_arg: usize },
/// The return value is `lhs_arg + rhs_arg`.
ReturnAdd { lhs_arg: usize, rhs_arg: usize },
/// The return value is `lhs_arg * rhs_arg`.
ReturnMul { lhs_arg: usize, rhs_arg: usize },
ReturnBoundedArithmetic {
lhs_arg: usize,
rhs_arg: usize,
op: BoundedArithmeticOp,
},
ReturnWithOverflow {
lhs_arg: usize,
rhs_arg: usize,
op: OverflowOp,
},
/// The return value is non-zero *iff* `arg` is non-zero (models bit-manipulating
/// intrinsics like `bswap`/`bitreverse`/`ctpop`/`rotate_*`, which map `0` to
/// `0` and non-zero to non-zero).
ReturnNonZeroIff { arg: usize },
/// The call returns `Option<T>` whose `Some` payload is unconditionally
/// non-zero (models `checked_next_power_of_two`, where the next power of
/// two is always positive regardless of the argument).
ReturnOptionSomeNonZero,
/// A specific field of the returned tuple carries the length of a given
/// argument (e.g. split_at(mid) returns (left, right) where left.len() == mid).
ReturnTupleFieldLength { field: usize, from_arg: usize },
/// The return value is a pointer backed by a fresh heap allocation of
/// `size_arg` elements × `elem_size` bytes. Unlike ReturnFreshAllocation
/// this does not require a pointer argument — used for constructors like
/// `Vec::from_elem(init, count)` that allocate fresh memory.
ReturnNewAllocation { size_arg: usize, elem_size: u64 },
/// `Box::new` / `Box::new_in` / `Box::new_uninit` / `Box::new_uninit_in`
/// (and `try_` variants): allocate a fresh heap buffer of `size_of::<T>()`
/// bytes and return a `Box` whose pointer field backs it. These have MIR
/// available but carry a `match` on the allocator's `Result`, which the
/// inline heuristic rejects as a semantic branch, so a direct effect is the
/// only way the fresh allocation's provenance reaches the `NonNull`.
ReturnBoxAllocation,
/// Like ReturnNewAllocation but the length is carried by the argument
/// itself (a Box fat pointer) rather than a separate count argument.
/// Used for `into_vec` / `box_assume_init_into_vec_unsafe`.
ReturnNewAllocationFromBox,
/// Like `ReturnNewAllocation`, but the argument is the *capacity*: the
/// returned Vec starts empty (`len == 0`) with `cap == cap_arg` (models
/// `Vec::with_capacity`).
ReturnNewAllocationFromCap { cap_arg: usize, elem_size: u64 },
/// The return value is a non-zero power of two (models `Layout::align`).
ReturnPowerOfTwo,
/// The call transfers a Vec's backing allocation into a Box (e.g.
/// `Vec::into_boxed_slice`). Looks up the current heap allocation from the
/// argument's owning pointer field via its stack provenance.
ReturnBoxFromVec { arg: usize },
/// The return value is known to own initialized memory of the type pointed
/// to by the indicated argument (e.g. `Box::from_raw(p)` owns one initialized
/// `T` element reached through `p`).
OwnsInitMemory { arg: usize },
/// The call returns `Option<usize>` whose `Some` payload is a scan index
/// into the iterator argument `self_arg` (models `Iterator::position` /
/// `Iterator::find`): `Some(i)` satisfies `0 <= i < self.len()` where
/// `self` is the Iter/IterMut struct produced by `into_iter`/`iter`.
ReturnOptionSomeScanIndex { self_arg: usize },
/// The call is `Try::branch`: `Option<T>` -> `ControlFlow<Option<!>, T>`,
/// so the result's `Continue` payload (field 0) equals the input's `Some`
/// payload (field 0). Models the `?` operator's `if let Some(..) = expr?`
/// unwrap so the payload's provenance survives the branch.
ReturnBranchPayload { arg: usize },
/// `ptr.align_offset(align)` returns an offset such that
/// `(ptr + offset) % align == 0` and `0 <= offset < align` (or `usize::MAX`
/// when no such offset exists). Models `*const T::align_offset` /
/// `*mut T::align_offset` by recording the alignment path-condition so
/// downstream `ptr.add(offset)` dereferences can discharge `Align`.
ReturnAlignOffset { ptr_arg: usize, align_arg: usize },
/// `<ManuallyDrop<T> as Deref>::deref` / `MaybeDangling::as_ref` return a
/// reference to the inner value at the *same* address (transparent
/// wrappers). The return aliases `arg` (a `&T` pointing at `arg`'s
/// pointee) and its pointee field values are the argument's field values
/// with the leading `peel` transparent field-0 hops stripped.
ReturnTransparentDeref { arg: usize, peel: usize },
/// `slice::range(range, bounds)` returns `Range { start, end }` satisfying
/// `0 <= start <= end <= bounds.end`. Models the range normalizer whose
/// `start_bound`/`end_bound` trait dispatch cannot be inlined.
ReturnRange { bounds_arg: usize },
/// `mem::replace(dest, src)` returns `*dest` (the old value), so the return
/// is the *pointee* of the reference argument, not the reference itself.
ReturnDerefArg { arg: usize },
/// The call *frees* the heap allocation behind `pointer_arg` (a `&mut`
/// reference to a `Box`/`Vec`/`String` pointee). Models `ManuallyDrop::drop`.
DropMemory { pointer_arg: usize },
/// `<[T]>::index(range)` / `::index_mut(range)` returns a sub-slice whose
/// length is the range's extent. Modelled as a sub-allocation of the array
/// so downstream `into_iter`/`next()` see the correct element count.
ReturnSliceRangeIndex,
/// `Iter::len()` / `Iter::is_empty()` computed from the iterator's pointer
/// fields (`ptr` + `end_or_len` sharing the same allocation).
ReturnIterLen { is_len: bool },
/// `NonNull::<T>::new(ptr) -> Option<NonNull<T>>`: the safe constructor,
/// returning `Some(ptr)` when the pointer is provably non-null and an
/// unconstrained `Option` otherwise.
ReturnNonNullNew,
/// `Iter::next()` / `IterMut::next()`: return the current element pointer
/// and advance the iterator's tracked offset by one.
ReturnIterNext,
/// `Range<A>::next` / `RangeInclusive<A>::next`: return the current
/// `start` and advance it by one, carrying the `start < end` bound so a
/// downstream `InBound(arr, i)` can be discharged.
ReturnRangeNext,
/// `size_of::<T>()` / `align_of::<T>()` for a *generic* `T` (no concrete
/// layout): the result is the shared symbolic `sizeof_T` / `align_T`, bound
/// at apply time from `func`'s type argument.
ReturnLayoutSymbolic { is_size: bool },
}
impl CallEffect {
pub(super) fn written_args(&self) -> Vec<usize> {
match self {
Self::WriteMemory { pointer_arg }
| Self::DropMemory { pointer_arg }
| Self::FillBytes { pointer_arg, .. } => vec![*pointer_arg],
Self::CopyMemory { destination_arg, .. } => vec![*destination_arg],
Self::SwapMemory { left_arg, right_arg } => vec![*left_arg, *right_arg],
_ => Vec::new(),
}
}
pub(super) fn write_inputs(&self) -> Vec<usize> {
match self {
Self::FillBytes { pointer_arg, byte_arg, count_arg } => {
vec![*pointer_arg, *byte_arg, *count_arg]
}
Self::CopyMemory { source_arg, destination_arg, count_arg } => {
vec![*source_arg, *destination_arg, *count_arg]
}
_ => self.written_args(),
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum OverflowOp {
Add,
Sub,
Mul,
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum BoundedArithmeticOp {
SaturatingAdd,
SaturatingSub,
WrappingSub,
}