Debian Codegraph @

.cargo/vendor/zerocopy/src/byte_slice.rs

raw
1 // Copyright 2024 The Fuchsia Authors
2 //
3 // Licensed under a BSD-style license <LICENSE-BSD>, Apache License, Version 2.0
4 // <LICENSE-APACHE or https://www.apache.org/licenses/LICENSE-2.0>, or the MIT
5 // license <LICENSE-MIT or https://opensource.org/licenses/MIT>, at your option.
6 // This file may not be copied, modified, or distributed except according to
7 // those terms.
8
9 //! Traits for types that encapsulate a `[u8]`.
10 //!
11 //! These traits are used to bound the `B` parameter of [`Ref`].
12
13 use core::{
14 cell,
15 ops::{Deref, DerefMut},
16 };
17
18 // For each trait polyfill, as soon as the corresponding feature is stable, the
19 // polyfill import will be unused because method/function resolution will prefer
20 // the inherent method/function over a trait method/function. Thus, we suppress
21 // the `unused_imports` warning.
22 //
23 // See the documentation on `util::polyfills` for more information.
24 #[allow(unused_imports)]
25 use crate::util::polyfills::{self, NonNullExt as _, NumExt as _};
26 #[cfg(doc)]
27 use crate::Ref;
28
29 /// A mutable or immutable reference to a byte slice.
30 ///
31 /// `ByteSlice` abstracts over the mutability of a byte slice reference, and is
32 /// implemented for various special reference types such as
33 /// [`Ref<[u8]>`](core::cell::Ref) and [`RefMut<[u8]>`](core::cell::RefMut).
34 ///
35 /// # Safety
36 ///
37 /// Implementations of `ByteSlice` must promise that their implementations of
38 /// [`Deref`] and [`DerefMut`] are "stable". In particular, given `B: ByteSlice`
39 /// and `b: B`, two calls, each to either `b.deref()` or `b.deref_mut()`, must
40 /// return a byte slice with the same address and length. This must hold even if
41 /// the two calls are separated by an arbitrary sequence of calls to methods on
42 /// `ByteSlice`, [`ByteSliceMut`], [`IntoByteSlice`], or [`IntoByteSliceMut`],
43 /// or on their super-traits. This does *not* need to hold if the two calls are
44 /// separated by any method calls, field accesses, or field modifications *other
45 /// than* those from these traits.
46 ///
47 /// Note that this also implies that, given `b: B`, the address and length
48 /// cannot be modified via objects other than `b`, either on the same thread or
49 /// on another thread.
50 pub unsafe trait ByteSlice: Deref<Target = [u8]> + Sized {}
51
52 /// A mutable reference to a byte slice.
53 ///
54 /// `ByteSliceMut` abstracts over various ways of storing a mutable reference to
55 /// a byte slice, and is implemented for various special reference types such as
56 /// `RefMut<[u8]>`.
57 ///
58 /// `ByteSliceMut` is a shorthand for [`ByteSlice`] and [`DerefMut`].
59 pub trait ByteSliceMut: ByteSlice + DerefMut {}
60 impl<B: ByteSlice + DerefMut> ByteSliceMut for B {}
61
62 /// A [`ByteSlice`] which can be copied without violating dereference stability.
63 ///
64 /// # Safety
65 ///
66 /// If `B: CopyableByteSlice`, then the dereference stability properties
67 /// required by [`ByteSlice`] (see that trait's safety documentation) do not
68 /// only hold regarding two calls to `b.deref()` or `b.deref_mut()`, but also
69 /// hold regarding `c.deref()` or `c.deref_mut()`, where `c` is produced by
70 /// copying `b`.
71 pub unsafe trait CopyableByteSlice: ByteSlice + Copy + CloneableByteSlice {}
72
73 /// A [`ByteSlice`] which can be cloned without violating dereference stability.
74 ///
75 /// # Safety
76 ///
77 /// If `B: CloneableByteSlice`, then the dereference stability properties
78 /// required by [`ByteSlice`] (see that trait's safety documentation) do not
79 /// only hold regarding two calls to `b.deref()` or `b.deref_mut()`, but also
80 /// hold regarding `c.deref()` or `c.deref_mut()`, where `c` is produced by
81 /// `b.clone()`, `b.clone().clone()`, etc.
82 pub unsafe trait CloneableByteSlice: ByteSlice + Clone {}
83
84 /// A [`ByteSlice`] that can be split in two.
85 ///
86 /// # Safety
87 ///
88 /// Unsafe code may depend for its soundness on the assumption that `split_at`
89 /// and `split_at_unchecked` are implemented correctly. In particular, given `B:
90 /// SplitByteSlice` and `b: B`, if `b.deref()` returns a byte slice with address
91 /// `addr` and length `len`, then if `split <= len`, both of these
92 /// invocations:
93 /// - `b.split_at(split)`
94 /// - `b.split_at_unchecked(split)`
95 ///
96 /// ...will return `(first, second)` such that:
97 /// - `first`'s address is `addr` and its length is `split`
98 /// - `second`'s address is `addr + split` and its length is `len - split`
99 pub unsafe trait SplitByteSlice: ByteSlice {
100 /// Attempts to split `self` at the midpoint.
101 ///
102 /// `s.split_at(mid)` returns `Ok((s[..mid], s[mid..]))` if `mid <=
103 /// s.deref().len()` and otherwise returns `Err(s)`.
104 ///
105 /// # Safety
106 ///
107 /// Unsafe code may rely on this function correctly implementing the above
108 /// functionality.
109 #[inline]
110 fn split_at(self, mid: usize) -> Result<(Self, Self), Self> {
111 if mid <= self.deref().len() {
112 // SAFETY: Above, we ensure that `mid <= self.deref().len()`. By
113 // invariant on `ByteSlice`, a supertrait of `SplitByteSlice`,
114 // `.deref()` is guaranteed to be "stable"; i.e., it will always
115 // dereference to a byte slice of the same address and length. Thus,
116 // we can be sure that the above precondition remains satisfied
117 // through the call to `split_at_unchecked`.
118 unsafe { Ok(self.split_at_unchecked(mid)) }
119 } else {
120 Err(self)
121 }
122 }
123
124 /// Splits the slice at the midpoint, possibly omitting bounds checks.
125 ///
126 /// `s.split_at_unchecked(mid)` returns `s[..mid]` and `s[mid..]`.
127 ///
128 /// # Safety
129 ///
130 /// `mid` must not be greater than `self.deref().len()`.
131 ///
132 /// # Panics
133 ///
134 /// Implementations of this method may choose to perform a bounds check and
135 /// panic if `mid > self.deref().len()`. They may also panic for any other
136 /// reason. Since it is optional, callers must not rely on this behavior for
137 /// soundness.
138 #[must_use]
139 unsafe fn split_at_unchecked(self, mid: usize) -> (Self, Self);
140 }
141
142 /// A shorthand for [`SplitByteSlice`] and [`ByteSliceMut`].
143 pub trait SplitByteSliceMut: SplitByteSlice + ByteSliceMut {}
144 impl<B: SplitByteSlice + ByteSliceMut> SplitByteSliceMut for B {}
145
146 #[allow(clippy::missing_safety_doc)] // There's a `Safety` section on `into_byte_slice`.
147 /// A [`ByteSlice`] that conveys no ownership, and so can be converted into a
148 /// byte slice.
149 ///
150 /// Some `ByteSlice` types (notably, the standard library's [`Ref`] type) convey
151 /// ownership, and so they cannot soundly be moved by-value into a byte slice
152 /// type (`&[u8]`). Some methods in this crate's API (such as [`Ref::into_ref`])
153 /// are only compatible with `ByteSlice` types without these ownership
154 /// semantics.
155 ///
156 /// [`Ref`]: core::cell::Ref
157 pub unsafe trait IntoByteSlice<'a>: ByteSlice {
158 /// Coverts `self` into a `&[u8]`.
159 ///
160 /// # Safety
161 ///
162 /// The returned reference has the same address and length as `self.deref()`
163 /// and `self.deref_mut()`.
164 ///
165 /// Note that, combined with the safety invariant on [`ByteSlice`], this
166 /// safety invariant implies that the returned reference is "stable" in the
167 /// sense described in the `ByteSlice` docs.
168 fn into_byte_slice(self) -> &'a [u8];
169 }
170
171 #[allow(clippy::missing_safety_doc)] // There's a `Safety` section on `into_byte_slice_mut`.
172 /// A [`ByteSliceMut`] that conveys no ownership, and so can be converted into a
173 /// mutable byte slice.
174 ///
175 /// Some `ByteSliceMut` types (notably, the standard library's [`RefMut`] type)
176 /// convey ownership, and so they cannot soundly be moved by-value into a byte
177 /// slice type (`&mut [u8]`). Some methods in this crate's API (such as
178 /// [`Ref::into_mut`]) are only compatible with `ByteSliceMut` types without
179 /// these ownership semantics.
180 ///
181 /// [`RefMut`]: core::cell::RefMut
182 pub unsafe trait IntoByteSliceMut<'a>: IntoByteSlice<'a> + ByteSliceMut {
183 /// Coverts `self` into a `&mut [u8]`.
184 ///
185 /// # Safety
186 ///
187 /// The returned reference has the same address and length as `self.deref()`
188 /// and `self.deref_mut()`.
189 ///
190 /// Note that, combined with the safety invariant on [`ByteSlice`], this
191 /// safety invariant implies that the returned reference is "stable" in the
192 /// sense described in the `ByteSlice` docs.
193 fn into_byte_slice_mut(self) -> &'a mut [u8];
194 }
195
196 // FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
197 #[allow(clippy::undocumented_unsafe_blocks)]
198 unsafe impl ByteSlice for &[u8] {}
199
200 // FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
201 #[allow(clippy::undocumented_unsafe_blocks)]
202 unsafe impl CopyableByteSlice for &[u8] {}
203
204 // FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
205 #[allow(clippy::undocumented_unsafe_blocks)]
206 unsafe impl CloneableByteSlice for &[u8] {}
207
208 // SAFETY: This delegates to `polyfills:split_at_unchecked`, which is documented
209 // to correctly split `self` into two slices at the given `mid` point.
210 unsafe impl SplitByteSlice for &[u8] {
211 #[inline]
212 unsafe fn split_at_unchecked(self, mid: usize) -> (Self, Self) {
213 // SAFETY: By contract on caller, `mid` is not greater than
214 // `bytes.len()`.
215 unsafe { (<[u8]>::get_unchecked(self, ..mid), <[u8]>::get_unchecked(self, mid..)) }
216 }
217 }
218
219 // SAFETY: See inline.
220 unsafe impl<'a> IntoByteSlice<'a> for &'a [u8] {
221 #[inline(always)]
222 fn into_byte_slice(self) -> &'a [u8] {
223 // SAFETY: It would be patently insane to implement `<Deref for
224 // &[u8]>::deref` as anything other than `fn deref(&self) -> &[u8] {
225 // *self }`. Assuming this holds, then `self` is stable as required by
226 // `into_byte_slice`.
227 self
228 }
229 }
230
231 // FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
232 #[allow(clippy::undocumented_unsafe_blocks)]
233 unsafe impl ByteSlice for &mut [u8] {}
234
235 // SAFETY: This delegates to `polyfills:split_at_mut_unchecked`, which is
236 // documented to correctly split `self` into two slices at the given `mid`
237 // point.
238 unsafe impl SplitByteSlice for &mut [u8] {
239 #[inline]
240 unsafe fn split_at_unchecked(self, mid: usize) -> (Self, Self) {
241 use core::slice::from_raw_parts_mut;
242
243 // `l_ptr` is non-null, because `self` is non-null, by invariant on
244 // `&mut [u8]`.
245 let l_ptr = self.as_mut_ptr();
246
247 // SAFETY: By contract on caller, `mid` is not greater than
248 // `self.len()`.
249 let r_ptr = unsafe { l_ptr.add(mid) };
250
251 let l_len = mid;
252
253 // SAFETY: By contract on caller, `mid` is not greater than
254 // `self.len()`.
255 //
256 // FIXME(#67): Remove this allow. See NumExt for more details.
257 #[allow(unstable_name_collisions)]
258 let r_len = unsafe { self.len().unchecked_sub(mid) };
259
260 // SAFETY: These invocations of `from_raw_parts_mut` satisfy its
261 // documented safety preconditions [1]:
262 // - The data `l_ptr` and `r_ptr` are valid for both reads and writes of
263 // `l_len` and `r_len` bytes, respectively, and they are trivially
264 // aligned. In particular:
265 // - The entire memory range of each slice is contained within a
266 // single allocated object, since `l_ptr` and `r_ptr` are both
267 // derived from within the address range of `self`.
268 // - Both `l_ptr` and `r_ptr` are non-null and trivially aligned.
269 // `self` is non-null by invariant on `&mut [u8]`, and the
270 // operations that derive `l_ptr` and `r_ptr` from `self` do not
271 // nullify either pointer.
272 // - The data `l_ptr` and `r_ptr` point to `l_len` and `r_len`,
273 // respectively, consecutive properly initialized values of type `u8`.
274 // This is true for `self` by invariant on `&mut [u8]`, and remains
275 // true for these two sub-slices of `self`.
276 // - The memory referenced by the returned slice cannot be accessed
277 // through any other pointer (not derived from the return value) for
278 // the duration of lifetime `'a``, because:
279 // - `split_at_unchecked` consumes `self` (which is not `Copy`),
280 // - `split_at_unchecked` does not exfiltrate any references to this
281 // memory, besides those references returned below,
282 // - the returned slices are non-overlapping.
283 // - The individual sizes of the sub-slices of `self` are no larger than
284 // `isize::MAX`, because their combined sizes are no larger than
285 // `isize::MAX`, by invariant on `self`.
286 //
287 // [1] https://doc.rust-lang.org/std/slice/fn.from_raw_parts_mut.html#safety
288 unsafe { (from_raw_parts_mut(l_ptr, l_len), from_raw_parts_mut(r_ptr, r_len)) }
289 }
290 }
291
292 // SAFETY: See inline.
293 unsafe impl<'a> IntoByteSlice<'a> for &'a mut [u8] {
294 #[inline(always)]
295 fn into_byte_slice(self) -> &'a [u8] {
296 // SAFETY: It would be patently insane to implement `<Deref for &mut
297 // [u8]>::deref` as anything other than `fn deref(&self) -> &[u8] {
298 // *self }`. Assuming this holds, then `self` is stable as required by
299 // `into_byte_slice`.
300 self
301 }
302 }
303
304 // SAFETY: See inline.
305 unsafe impl<'a> IntoByteSliceMut<'a> for &'a mut [u8] {
306 #[inline(always)]
307 fn into_byte_slice_mut(self) -> &'a mut [u8] {
308 // SAFETY: It would be patently insane to implement `<DerefMut for &mut
309 // [u8]>::deref` as anything other than `fn deref_mut(&mut self) -> &mut
310 // [u8] { *self }`. Assuming this holds, then `self` is stable as
311 // required by `into_byte_slice_mut`.
312 self
313 }
314 }
315
316 // FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
317 #[allow(clippy::undocumented_unsafe_blocks)]
318 unsafe impl ByteSlice for cell::Ref<'_, [u8]> {}
319
320 // SAFETY: This delegates to stdlib implementation of `Ref::map_split`, which is
321 // assumed to be correct, and `SplitByteSlice::split_at_unchecked`, which is
322 // documented to correctly split `self` into two slices at the given `mid`
323 // point.
324 unsafe impl SplitByteSlice for cell::Ref<'_, [u8]> {
325 #[inline]
326 unsafe fn split_at_unchecked(self, mid: usize) -> (Self, Self) {
327 cell::Ref::map_split(self, |slice|
328 // SAFETY: By precondition on caller, `mid` is not greater than
329 // `slice.len()`.
330 unsafe {
331 SplitByteSlice::split_at_unchecked(slice, mid)
332 })
333 }
334 }
335
336 // FIXME(#429): Add a "SAFETY" comment and remove this `allow`.
337 #[allow(clippy::undocumented_unsafe_blocks)]
338 unsafe impl ByteSlice for cell::RefMut<'_, [u8]> {}
339
340 // SAFETY: This delegates to stdlib implementation of `RefMut::map_split`, which
341 // is assumed to be correct, and `SplitByteSlice::split_at_unchecked`, which is
342 // documented to correctly split `self` into two slices at the given `mid`
343 // point.
344 unsafe impl SplitByteSlice for cell::RefMut<'_, [u8]> {
345 #[inline]
346 unsafe fn split_at_unchecked(self, mid: usize) -> (Self, Self) {
347 cell::RefMut::map_split(self, |slice|
348 // SAFETY: By precondition on caller, `mid` is not greater than
349 // `slice.len()`
350 unsafe {
351 SplitByteSlice::split_at_unchecked(slice, mid)
352 })
353 }
354 }
355
356 #[cfg(kani)]
357 mod proofs {
358 use super::*;
359
360 fn any_vec() -> Vec<u8> {
361 let len = kani::any();
362 kani::assume(len <= isize::MAX as usize);
363 vec![0u8; len]
364 }
365
366 #[kani::proof]
367 fn prove_split_at_unchecked() {
368 let v = any_vec();
369 let slc = v.as_slice();
370 let mid = kani::any();
371 kani::assume(mid <= slc.len());
372 let (l, r) = unsafe { slc.split_at_unchecked(mid) };
373 assert_eq!(l.len() + r.len(), slc.len());
374
375 let slc: *const _ = slc;
376 let l: *const _ = l;
377 let r: *const _ = r;
378
379 assert_eq!(slc.cast::<u8>(), l.cast::<u8>());
380 assert_eq!(unsafe { slc.cast::<u8>().add(mid) }, r.cast::<u8>());
381
382 let mut v = any_vec();
383 let slc = v.as_mut_slice();
384 let len = slc.len();
385 let mid = kani::any();
386 kani::assume(mid <= slc.len());
387 let (l, r) = unsafe { slc.split_at_unchecked(mid) };
388 assert_eq!(l.len() + r.len(), len);
389
390 let l: *mut _ = l;
391 let r: *mut _ = r;
392 let slc: *mut _ = slc;
393
394 assert_eq!(slc.cast::<u8>(), l.cast::<u8>());
395 assert_eq!(unsafe { slc.cast::<u8>().add(mid) }, r.cast::<u8>());
396 }
397 }