1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5#![allow(clippy::upper_case_acronyms)]
6
7//! Traits over unaligned little-endian data (ULE, pronounced "yule").
8//!
9//! The main traits for this module are [`ULE`], [`AsULE`] and, [`VarULE`].
10//!
11//! See [the design doc](https://github.com/unicode-org/icu4x/blob/main/utils/zerovec/design_doc.md) for details on how these traits
12//! works under the hood.
13mod chars;
14#[cfg(doc)]
15pub mod custom;
16mod encode;
17mod macros;
18mod multi;
19mod niche;
20mod option;
21mod plain;
22mod slices;
23mod unvalidated;
24
25pub mod tuple;
26pub use super::ZeroVecError;
27pub use chars::CharULE;
28pub use encode::{encode_varule_to_box, EncodeAsVarULE};
29pub use multi::MultiFieldsULE;
30pub use niche::{NicheBytes, NichedOption, NichedOptionULE};
31pub use option::{OptionULE, OptionVarULE};
32pub use plain::RawBytesULE;
33pub use unvalidated::{UnvalidatedChar, UnvalidatedStr};
34
35use alloc::alloc::Layout;
36use alloc::borrow::ToOwned;
37use alloc::boxed::Box;
38use core::{mem, slice};
39
40/// Fixed-width, byte-aligned data that can be cast to and from a little-endian byte slice.
41///
42/// If you need to implement this trait, consider using [`#[make_ule]`](crate::make_ule) or
43/// [`#[derive(ULE)]`](macro@ULE) instead.
44///
45/// Types that are not fixed-width can implement [`VarULE`] instead.
46///
47/// "ULE" stands for "Unaligned little-endian"
48///
49/// # Safety
50///
51/// Safety checklist for `ULE`:
52///
53/// 1. The type *must not* include any uninitialized or padding bytes.
54/// 2. The type must have an alignment of 1 byte.
55/// 3. The impl of [`ULE::validate_byte_slice()`] *must* return an error if the given byte slice
56/// would not represent a valid slice of this type.
57/// 4. The impl of [`ULE::validate_byte_slice()`] *must* return an error if the given byte slice
58/// cannot be used in its entirety (if its length is not a multiple of `size_of::<Self>()`).
59/// 5. All other methods *must* be left with their default impl, or else implemented according to
60/// their respective safety guidelines.
61/// 6. Acknowledge the following note about the equality invariant.
62///
63/// If the ULE type is a struct only containing other ULE types (or other types which satisfy invariants 1 and 2,
64/// like `[u8; N]`), invariants 1 and 2 can be achieved via `#[repr(C, packed)]` or `#[repr(transparent)]`.
65///
66/// # Equality invariant
67///
68/// A non-safety invariant is that if `Self` implements `PartialEq`, the it *must* be logically
69/// equivalent to byte equality on [`Self::as_byte_slice()`].
70///
71/// It may be necessary to introduce a "canonical form" of the ULE if logical equality does not
72/// equal byte equality. In such a case, [`Self::validate_byte_slice()`] should return an error
73/// for any values that are not in canonical form. For example, the decimal strings "1.23e4" and
74/// "12.3e3" are logically equal, but not byte-for-byte equal, so we could define a canonical form
75/// where only a single digit is allowed before `.`.
76///
77/// Failure to follow this invariant will cause surprising behavior in `PartialEq`, which may
78/// result in unpredictable operations on `ZeroVec`, `VarZeroVec`, and `ZeroMap`.
79pub unsafe trait ULE
80where
81 Self: Sized,
82 Self: Copy + 'static,
83{
84 /// Validates a byte slice, `&[u8]`.
85 ///
86 /// If `Self` is not well-defined for all possible bit values, the bytes should be validated.
87 /// If the bytes can be transmuted, *in their entirety*, to a valid slice of `Self`, then `Ok`
88 /// should be returned; otherwise, `Self::Error` should be returned.
89 fn validate_byte_slice(bytes: &[u8]) -> Result<(), ZeroVecError>;
90
91 /// Parses a byte slice, `&[u8]`, and return it as `&[Self]` with the same lifetime.
92 ///
93 /// If `Self` is not well-defined for all possible bit values, the bytes should be validated,
94 /// and an error should be returned in the same cases as [`Self::validate_byte_slice()`].
95 ///
96 /// The default implementation executes [`Self::validate_byte_slice()`] followed by
97 /// [`Self::from_byte_slice_unchecked`].
98 ///
99 /// Note: The following equality should hold: `bytes.len() % size_of::<Self>() == 0`. This
100 /// means that the returned slice can span the entire byte slice.
101 fn parse_byte_slice(bytes: &[u8]) -> Result<&[Self], ZeroVecError> {
102 Self::validate_byte_slice(bytes)?;
103 debug_assert_eq!(bytes.len() % mem::size_of::<Self>(), 0);
104 Ok(unsafe { Self::from_byte_slice_unchecked(bytes) })
105 }
106
107 /// Takes a byte slice, `&[u8]`, and return it as `&[Self]` with the same lifetime, assuming
108 /// that this byte slice has previously been run through [`Self::parse_byte_slice()`] with
109 /// success.
110 ///
111 /// The default implementation performs a pointer cast to the same region of memory.
112 ///
113 /// # Safety
114 ///
115 /// ## Callers
116 ///
117 /// Callers of this method must take care to ensure that `bytes` was previously passed through
118 /// [`Self::validate_byte_slice()`] with success (and was not changed since then).
119 ///
120 /// ## Implementors
121 ///
122 /// Implementations of this method may call unsafe functions to cast the pointer to the correct
123 /// type, assuming the "Callers" invariant above.
124 ///
125 /// Keep in mind that `&[Self]` and `&[u8]` may have different lengths.
126 ///
127 /// Safety checklist:
128 ///
129 /// 1. This method *must* return the same result as [`Self::parse_byte_slice()`].
130 /// 2. This method *must* return a slice to the same region of memory as the argument.
131 #[inline]
132 unsafe fn from_byte_slice_unchecked(bytes: &[u8]) -> &[Self] {
133 let data = bytes.as_ptr();
134 let len = bytes.len() / mem::size_of::<Self>();
135 debug_assert_eq!(bytes.len() % mem::size_of::<Self>(), 0);
136 core::slice::from_raw_parts(data as *const Self, len)
137 }
138
139 /// Given `&[Self]`, returns a `&[u8]` with the same lifetime.
140 ///
141 /// The default implementation performs a pointer cast to the same region of memory.
142 ///
143 /// # Safety
144 ///
145 /// Implementations of this method should call potentially unsafe functions to cast the
146 /// pointer to the correct type.
147 ///
148 /// Keep in mind that `&[Self]` and `&[u8]` may have different lengths.
149 #[inline]
150 #[allow(clippy::wrong_self_convention)] // https://github.com/rust-lang/rust-clippy/issues/7219
151 fn as_byte_slice(slice: &[Self]) -> &[u8] {
152 unsafe {
153 slice::from_raw_parts(slice as *const [Self] as *const u8, mem::size_of_val(slice))
154 }
155 }
156}
157
158/// A trait for any type that has a 1:1 mapping with an unaligned little-endian (ULE) type.
159///
160/// If you need to implement this trait, consider using [`#[make_ule]`](crate::make_ule) instead.
161pub trait AsULE: Copy {
162 /// The ULE type corresponding to `Self`.
163 ///
164 /// Types having infallible conversions from all bit values (Plain Old Data) can use
165 /// `RawBytesULE` with the desired width; for example, `u32` uses `RawBytesULE<4>`.
166 ///
167 /// Types that are not well-defined for all bit values should implement a custom ULE.
168 type ULE: ULE;
169
170 /// Converts from `Self` to `Self::ULE`.
171 ///
172 /// This function may involve byte order swapping (native-endian to little-endian).
173 ///
174 /// For best performance, mark your implementation of this function `#[inline]`.
175 fn to_unaligned(self) -> Self::ULE;
176
177 /// Converts from `Self::ULE` to `Self`.
178 ///
179 /// This function may involve byte order swapping (little-endian to native-endian).
180 ///
181 /// For best performance, mark your implementation of this function `#[inline]`.
182 ///
183 /// # Safety
184 ///
185 /// This function is infallible because bit validation should have occurred when `Self::ULE`
186 /// was first constructed. An implementation may therefore involve an `unsafe{}` block, like
187 /// `from_bytes_unchecked()`.
188 fn from_unaligned(unaligned: Self::ULE) -> Self;
189}
190
191/// An [`EqULE`] type is one whose byte sequence equals the byte sequence of its ULE type on
192/// little-endian platforms. This enables certain performance optimizations, such as
193/// [`ZeroVec::try_from_slice`](crate::ZeroVec::try_from_slice).
194///
195/// # Implementation safety
196///
197/// This trait is safe to implement if the type's ULE (as defined by `impl `[`AsULE`]` for T`)
198/// has an equal byte sequence as the type itself on little-endian platforms; i.e., one where
199/// `*const T` can be cast to a valid `*const T::ULE`.
200pub unsafe trait EqULE: AsULE {}
201
202/// A trait for a type where aligned slices can be cast to unaligned slices.
203///
204/// Auto-implemented on all types implementing [`EqULE`].
205pub trait SliceAsULE
206where
207 Self: AsULE + Sized,
208{
209 /// Converts from `&[Self]` to `&[Self::ULE]` if possible.
210 ///
211 /// In general, this function returns `Some` on little-endian and `None` on big-endian.
212 fn slice_to_unaligned(slice: &[Self]) -> Option<&[Self::ULE]>;
213}
214
215#[cfg(target_endian = "little")]
216impl<T> SliceAsULE for T
217where
218 T: EqULE,
219{
220 #[inline]
221 fn slice_to_unaligned(slice: &[Self]) -> Option<&[Self::ULE]> {
222 // This is safe because on little-endian platforms, the byte sequence of &[T]
223 // is equivalent to the byte sequence of &[T::ULE] by the contract of EqULE,
224 // and &[T::ULE] has equal or looser alignment than &[T].
225 let ule_slice: &[::ULE] =
226 unsafe { core::slice::from_raw_parts(data:slice.as_ptr() as *const Self::ULE, slice.len()) };
227 Some(ule_slice)
228 }
229}
230
231#[cfg(not(target_endian = "little"))]
232impl<T> SliceAsULE for T
233where
234 T: EqULE,
235{
236 #[inline]
237 fn slice_to_unaligned(_: &[Self]) -> Option<&[Self::ULE]> {
238 None
239 }
240}
241
242/// Variable-width, byte-aligned data that can be cast to and from a little-endian byte slice.
243///
244/// If you need to implement this trait, consider using [`#[make_varule]`](crate::make_varule) or
245/// [`#[derive(VarULE)]`](macro@VarULE) instead.
246///
247/// This trait is mostly for unsized types like `str` and `[T]`. It can be implemented on sized types;
248/// however, it is much more preferable to use [`ULE`] for that purpose. The [`custom`] module contains
249/// additional documentation on how this type can be implemented on custom types.
250///
251/// If deserialization with `VarZeroVec` is desired is recommended to implement `Deserialize` for
252/// `Box<T>` (serde does not do this automatically for unsized `T`).
253///
254/// For convenience it is typically desired to implement [`EncodeAsVarULE`] and [`ZeroFrom`](zerofrom::ZeroFrom)
255/// on some stack type to convert to and from the ULE type efficiently when necessary.
256///
257/// # Safety
258///
259/// Safety checklist for `VarULE`:
260///
261/// 1. The type *must not* include any uninitialized or padding bytes.
262/// 2. The type must have an alignment of 1 byte.
263/// 3. The impl of [`VarULE::validate_byte_slice()`] *must* return an error if the given byte slice
264/// would not represent a valid slice of this type.
265/// 4. The impl of [`VarULE::validate_byte_slice()`] *must* return an error if the given byte slice
266/// cannot be used in its entirety.
267/// 5. The impl of [`VarULE::from_byte_slice_unchecked()`] must produce a reference to the same
268/// underlying data assuming that the given bytes previously passed validation.
269/// 6. All other methods *must* be left with their default impl, or else implemented according to
270/// their respective safety guidelines.
271/// 7. Acknowledge the following note about the equality invariant.
272///
273/// If the ULE type is a struct only containing other ULE/VarULE types (or other types which satisfy invariants 1 and 2,
274/// like `[u8; N]`), invariants 1 and 2 can be achieved via `#[repr(C, packed)]` or `#[repr(transparent)]`.
275///
276/// # Equality invariant
277///
278/// A non-safety invariant is that if `Self` implements `PartialEq`, the it *must* be logically
279/// equivalent to byte equality on [`Self::as_byte_slice()`].
280///
281/// It may be necessary to introduce a "canonical form" of the ULE if logical equality does not
282/// equal byte equality. In such a case, [`Self::validate_byte_slice()`] should return an error
283/// for any values that are not in canonical form. For example, the decimal strings "1.23e4" and
284/// "12.3e3" are logically equal, but not byte-for-byte equal, so we could define a canonical form
285/// where only a single digit is allowed before `.`.
286///
287/// There may also be cases where a `VarULE` has muiltiple canonical forms, such as a faster
288/// version and a smaller version. The cleanest way to handle this case would be separate types.
289/// However, if this is not feasible, then the application should ensure that the data it is
290/// deserializing is in the expected form. For example, if the data is being loaded from an
291/// external source, then requests could carry information about the expected form of the data.
292///
293/// Failure to follow this invariant will cause surprising behavior in `PartialEq`, which may
294/// result in unpredictable operations on `ZeroVec`, `VarZeroVec`, and `ZeroMap`.
295pub unsafe trait VarULE: 'static {
296 /// Validates a byte slice, `&[u8]`.
297 ///
298 /// If `Self` is not well-defined for all possible bit values, the bytes should be validated.
299 /// If the bytes can be transmuted, *in their entirety*, to a valid `&Self`, then `Ok` should
300 /// be returned; otherwise, `Self::Error` should be returned.
301 fn validate_byte_slice(_bytes: &[u8]) -> Result<(), ZeroVecError>;
302
303 /// Parses a byte slice, `&[u8]`, and return it as `&Self` with the same lifetime.
304 ///
305 /// If `Self` is not well-defined for all possible bit values, the bytes should be validated,
306 /// and an error should be returned in the same cases as [`Self::validate_byte_slice()`].
307 ///
308 /// The default implementation executes [`Self::validate_byte_slice()`] followed by
309 /// [`Self::from_byte_slice_unchecked`].
310 ///
311 /// Note: The following equality should hold: `size_of_val(result) == size_of_val(bytes)`,
312 /// where `result` is the successful return value of the method. This means that the return
313 /// value spans the entire byte slice.
314 fn parse_byte_slice(bytes: &[u8]) -> Result<&Self, ZeroVecError> {
315 Self::validate_byte_slice(bytes)?;
316 let result = unsafe { Self::from_byte_slice_unchecked(bytes) };
317 debug_assert_eq!(mem::size_of_val(result), mem::size_of_val(bytes));
318 Ok(result)
319 }
320
321 /// Takes a byte slice, `&[u8]`, and return it as `&Self` with the same lifetime, assuming
322 /// that this byte slice has previously been run through [`Self::parse_byte_slice()`] with
323 /// success.
324 ///
325 /// # Safety
326 ///
327 /// ## Callers
328 ///
329 /// Callers of this method must take care to ensure that `bytes` was previously passed through
330 /// [`Self::validate_byte_slice()`] with success (and was not changed since then).
331 ///
332 /// ## Implementors
333 ///
334 /// Implementations of this method may call unsafe functions to cast the pointer to the correct
335 /// type, assuming the "Callers" invariant above.
336 ///
337 /// Safety checklist:
338 ///
339 /// 1. This method *must* return the same result as [`Self::parse_byte_slice()`].
340 /// 2. This method *must* return a slice to the same region of memory as the argument.
341 unsafe fn from_byte_slice_unchecked(bytes: &[u8]) -> &Self;
342
343 /// Given `&Self`, returns a `&[u8]` with the same lifetime.
344 ///
345 /// The default implementation performs a pointer cast to the same region of memory.
346 ///
347 /// # Safety
348 ///
349 /// Implementations of this method should call potentially unsafe functions to cast the
350 /// pointer to the correct type.
351 #[inline]
352 fn as_byte_slice(&self) -> &[u8] {
353 unsafe { slice::from_raw_parts(self as *const Self as *const u8, mem::size_of_val(self)) }
354 }
355
356 /// Allocate on the heap as a `Box<T>`
357 #[inline]
358 fn to_boxed(&self) -> Box<Self> {
359 let bytesvec = self.as_byte_slice().to_owned().into_boxed_slice();
360 let bytesvec = mem::ManuallyDrop::new(bytesvec);
361 unsafe {
362 // Get the pointer representation
363 let ptr: *mut Self =
364 Self::from_byte_slice_unchecked(&bytesvec) as *const Self as *mut Self;
365 assert_eq!(Layout::for_value(&*ptr), Layout::for_value(&**bytesvec));
366 // Transmute the pointer to an owned pointer
367 Box::from_raw(ptr)
368 }
369 }
370}
371
372// Proc macro reexports
373//
374// These exist so that our docs can use intra-doc links.
375// Due to quirks of how rustdoc does documentation on reexports, these must be in this module and not reexported from
376// a submodule
377
378/// Custom derive for [`ULE`].
379///
380/// This can be attached to [`Copy`] structs containing only [`ULE`] types.
381///
382/// Most of the time, it is recommended one use [`#[make_ule]`](crate::make_ule) instead of defining
383/// a custom ULE type.
384#[cfg(feature = "derive")]
385pub use zerovec_derive::ULE;
386
387/// Custom derive for [`VarULE`]
388///
389/// This can be attached to structs containing only [`ULE`] types with one [`VarULE`] type at the end.
390///
391/// Most of the time, it is recommended one use [`#[make_varule]`](crate::make_varule) instead of defining
392/// a custom [`VarULE`] type.
393#[cfg(feature = "derive")]
394pub use zerovec_derive::VarULE;
395