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