rel_ptr/lib.rs
1#![cfg_attr(feature = "no_std", no_std)]
2#![cfg_attr(feature = "nightly", feature(const_fn, raw))]
3#![forbid(missing_docs)]
4
5/*!
6 # rel-ptr
7
8 `rel-ptr` a library for relative pointers, which can be used to create
9 moveable self-referential types. This library was inspired by
10 Johnathan Blow's work on Jai, where he added relative pointers
11 as a primitive into Jai.
12
13 A relative pointer is a pointer that uses an offset and it's current location to
14 calculate where it points to.
15
16 ## Safety
17
18 See the `RelPtr` type docs for safety information
19
20 ## Features
21
22 ### `no_std`
23
24 This crate is `no-std` compatible, simply add the feature `no_std` to move into `no_std` mode.
25
26 ### nightly
27
28 with nightly you get the ability to use trait objects with relative pointers
29
30 ## Example
31
32 take the memory segment below
33
34 `[.., 0x3a, 0x10, 0x02, 0xe4, 0x2b ..]`
35
36 where `0x3a` has the address `0xff304050` (32-bit system)
37 then `0x2b` has the address `0xff304054`.
38
39 if we have a 1-byte relative pointer (`RelPtr<_, i8>`)
40 at the address `0xff304052`, then that relative pointer points to
41 `0x2b` as well, this is because its address `0xff304052`, plus its
42 offset, `0x02` points to `0x2b`.
43
44 There are three interesting things
45 about this
46 1) it only took 1 byte to point to another value,
47 2) a relative pointer cannot access all memory, only memory near it
48 3) if both the relative pointer and the pointee move together,
49 then the relative pointer will not be invalidated
50
51 The third point is what makes moveable self-referential structs possible
52
53 The type `RelPtr<T, I>` is a relative pointer. `T` is what it points to,
54 and `I` is what it uses to store its offset. In practice you can ignore `I`,
55 which is defaulted to `isize`, because that will cover all of your cases for using
56 relative pointers. But if you want to optimize the size of the pointer, you can use
57 any type that implements `Delta`. Some types from std that do so are:
58 `i8`, `i16`, `i32`, `i64`, `i128`, and `isize`. Note that the trade off is that as you
59 decrease the size of the offset, you decrease the range to which you can point to.
60 `isize` will cover at least half of addressable memory, so it should work unless you do
61 something really crazy. For self-referential structs use a type whose max value is atleast
62 as big as your struct. i.e. `std::mem::size_of::<T>() <= I::max_value()`.
63
64 Note on usized types: these are harder to get working
65
66 ## Self Referential Type Example
67
68 ```rust
69 # fn main() {
70 # use rel_ptr::RelPtr;
71 struct SelfRef {
72 value: (String, u32),
73 ptr: RelPtr<String, i8>
74 }
75
76 impl SelfRef {
77 pub fn new(s: String, i: u32) -> Self {
78 let mut this = Self {
79 value: (s, i),
80 ptr: RelPtr::null()
81 };
82
83 this.ptr.set(&mut this.value.0).unwrap();
84
85 this
86 }
87
88 pub fn fst(&self) -> &str {
89 unsafe { self.ptr.as_ref_unchecked() }
90 }
91
92 pub fn snd(&self) -> u32 {
93 self.value.1
94 }
95 }
96
97 let s = SelfRef::new("Hello World".into(), 10);
98
99 assert_eq!(s.fst(), "Hello World");
100 assert_eq!(s.snd(), 10);
101
102 let s = Box::new(s); // force a move, note: relative pointers even work on the heap
103
104 assert_eq!(s.fst(), "Hello World");
105 assert_eq!(s.snd(), 10);
106 # }
107 ```
108
109 This example is contrived, and only useful as an example.
110 In this example, we can see a few important parts to safe moveable self-referential types,
111 lets walk through them.
112
113 First, the definition of `SelfRef`, it contains a value and a relative pointer, the relative pointer that will point into the tuple inside of `SelfRef.value` to the `String`. There are no lifetimes involved because they would either make `SelfRef` immovable, or they could not be resolved correctly.
114
115 We see a pattern inside of `SelfRef::new`, first create the object, and use the sentinel `RelPtr::null()` and immediately afterwards assigning it a value using `RelPtr::set` and unwraping the result. This unwrapping is get quick feedback on whether or not the pointer was set, if it wasn't set then we can increase the size of the offset and resolve that.
116
117 Once the pointer is set, moving the struct is still safe because it is using a *relative* pointer, so it doesn't matter where it is, only it's offset from its pointee.
118 In `SelfRef::fst` we use `RelPtr::as_ref_unchecked` because it is impossible to invalidate the pointer. It is impossible because we cannot
119 set the relative pointer directly, and we cannot change the offsets of the fields of `SelfRef` after the relative pointer is set.
120*/
121
122#[cfg(feature = "no_std")]
123extern crate core as std;
124
125#[cfg(test)]
126mod tests;
127
128#[cfg(feature = "nightly")]
129mod nightly;
130
131mod traits;
132mod error;
133mod fmt;
134
135mod maybe_uninit;
136mod unreachable;
137
138#[cfg(feature = "nightly")]
139pub use self::nightly::*;
140pub use self::traits::*;
141pub use self::error::*;
142
143use self::maybe_uninit::*;
144
145use crate::unreachable::UncheckedOptionExt as _;
146
147use std::marker::PhantomData;
148use std::ptr::NonNull;
149use core::num::*;
150
151macro_rules! impl_delta_zeroable {
152 ($($type:ty),* $(,)?) => {$(
153 unsafe impl Delta for $type {
154 type Error = IntegerDeltaError;
155
156 fn sub(a: *mut u8, b: *mut u8) -> Result<Self, Self::Error> {
157 let del = match isize::checked_sub(a as usize as _, b as usize as _) {
158 Some(del) => del,
159 None => return Err(IntegerDeltaError(IntegerDeltaErrorImpl::Sub(a as usize, b as usize)))
160 };
161
162 if std::mem::size_of::<Self>() < std::mem::size_of::<isize>() && (
163 (Self::min_value() as isize) > del ||
164 (Self::max_value() as isize) < del
165 )
166 {
167 Err(IntegerDeltaError(IntegerDeltaErrorImpl::Conversion(del)))
168 } else {
169 Ok(del as _)
170 }
171 }
172
173 unsafe fn sub_unchecked(a: *mut u8, b: *mut u8) -> Self {
174 isize::checked_sub(a as usize as _, b as usize as _).unchecked_unwrap() as _
175 }
176
177 unsafe fn add(self, a: *const u8) -> *mut u8 {
178 <*const u8>::offset(a, self as isize) as *mut u8
179 }
180 }
181
182 impl Nullable for $type {
183 const NULL: Self = 0;
184 }
185 )*};
186}
187
188impl_delta_zeroable! { i8, i16, i32, i64, i128, isize }
189
190macro_rules! impl_delta_nonzero {
191 ($($type:ident $base:ident),* $(,)?) => {$(
192 unsafe impl Delta for $type {
193 type Error = IntegerDeltaError;
194
195 fn sub(a: *mut u8, b: *mut u8) -> Result<Self, Self::Error> {
196 let del = match isize::checked_sub(a as usize as _, b as usize as _) {
197 None => return Err(IntegerDeltaError(IntegerDeltaErrorImpl::Sub(a as usize, b as usize))),
198 Some(0) => return Err(IntegerDeltaError(IntegerDeltaErrorImpl::InvalidNonZero)),
199 Some(del) => del,
200 };
201
202 if std::mem::size_of::<Self>() < std::mem::size_of::<isize>() && (
203 ($base::min_value() as isize) > del ||
204 ($base::max_value() as isize) < del
205 )
206 {
207 Err(IntegerDeltaError(IntegerDeltaErrorImpl::Conversion(del)))
208 } else {
209 // 0 case was checked in match before hand, so this is guarenteed ot be non zero
210 unsafe { Ok(Self::new_unchecked(del as _)) }
211 }
212 }
213
214 unsafe fn sub_unchecked(a: *mut u8, b: *mut u8) -> Self {
215 Self::new_unchecked(isize::checked_sub(a as usize as _, b as usize as _).unchecked_unwrap() as _)
216 }
217
218 unsafe fn add(self, a: *const u8) -> *mut u8 {
219 <*mut u8>::offset(a as _, self.get() as isize) as *mut u8
220 }
221 }
222 )*};
223}
224
225impl_delta_nonzero! { NonZeroI8 i8, NonZeroI16 i16, NonZeroI32 i32, NonZeroI64 i64, NonZeroI128 i128, NonZeroIsize isize }
226
227/// It is always safe to cast between a
228/// `Option<NonNull<T>>` and a `*mut T`
229/// because they are the exact same in memory
230#[inline(always)]
231fn nn_to_ptr<T: ?Sized>(nn: Ptr<T>) -> *mut T {
232 unsafe { std::mem::transmute(nn) }
233}
234
235/**
236 * This represents a relative pointers
237 *
238 * A relative pointer stores an offset, and uses its
239 * that in combination with its current position in memory
240 * to point to a value
241 *
242 * See crate documentation for more information
243 *
244 * # Safety
245 *
246 * When using `core::num::NonZero*`, it is UB to have the `RelPtr` point to itself, this could be achieved
247 * with
248 *
249 * If you use `RelPtr::from(offset)`, then you must ensure that the relative pointer is set with the
250 * given functions to avoid UB
251 *
252 * When using `RelPtr` with packed structs it is important to keep in mind that packed struct move fields
253 * to align them to drop them. For example, the below example is UB
254 *
255 * ```ignore
256 * #[repr(packed)]
257 * struct Base(String, UnsafeThing);
258 *
259 * struct UnsafeThing(RelPtr<String>); // points into Base
260 *
261 * impl Drop for UnsafeThing {
262 * fn drop(&mut self) {
263 * // ... accessing `RelPtr<String>` here is UB
264 * }
265 * }
266 * ```
267 *
268 * This is because when `Base` drops, all of the fields are moved to align them. So the offset between the `String` in
269 * unsafe thing and the `RelPtr<String>` in `UnsafeThing` could be changed. This will result in UB if you try to access
270 * String inside of `UnsafeThing` even if you enforce drop order!
271*/
272pub struct RelPtr<T: ?Sized + MetaData, I: Delta = isize>(I, MaybeUninit<T::Data>, PhantomData<*mut T>);
273
274// Ergonomics and ptr like impls
275
276impl<T: ?Sized + MetaData, I: Delta> Copy for RelPtr<T, I> {}
277impl<T: ?Sized + MetaData, I: Delta> Clone for RelPtr<T, I> {
278 fn clone(&self) -> Self {
279 *self
280 }
281}
282
283impl<T: ?Sized + MetaData, I: Delta> Eq for RelPtr<T, I> {}
284impl<T: ?Sized + MetaData, I: Delta> PartialEq for RelPtr<T, I> {
285 fn eq(&self, other: &Self) -> bool {
286 std::ptr::eq(self, other)
287 }
288}
289
290/// Convert an offset into a `RelPtr`
291impl<T: ?Sized + MetaData, I: Delta> From<I> for RelPtr<T, I> {
292 fn from(i: I) -> Self {
293 Self(i, MaybeUninit::null(), PhantomData)
294 }
295}
296
297// Core api
298
299impl<T: ?Sized + MetaData, I: Nullable> RelPtr<T, I> {
300 /// A null relative pointer has an offset of 0, (points to itself)
301 #[inline(always)]
302 pub fn null() -> Self {
303 Self(I::NULL, MaybeUninit::null(), PhantomData)
304 }
305
306 /// Check if relative pointer is null
307 #[inline(always)]
308 pub fn is_null(&self) -> bool {
309 self.0 == I::NULL
310 }
311}
312
313impl<T: ?Sized + MetaData, I: Delta> RelPtr<T, I> {
314 /**
315 * Set the offset of a relative pointer,
316 * if the offset cannot be calculated using the given
317 * `Delta`, then `Err` will be returned, and there will be
318 * **no** change to the offset
319 */
320 #[inline]
321 pub fn set(&mut self, value: &mut T) -> Result<(), I::Error> {
322 self.0 = I::sub(value as *mut T as _, self as *mut Self as _)?;
323 self.1.set(T::data(value));
324
325 Ok(())
326 }
327
328 /**
329 * Set the offset of a relative pointer,
330 *
331 * # Safety
332 *
333 * if the offset is out of bounds for the given `Delta`
334 * then it's value is UB
335 *
336 * if the given pointer is null, this is UB
337 */
338 #[inline]
339 pub unsafe fn set_unchecked(&mut self, value: *mut T) {
340 self.0 = I::sub_unchecked(value as *mut T as _, self as *mut Self as _);
341 self.1.set(T::data(&*value));
342 }
343
344 /**
345 * Converts the relative pointer into a normal raw pointer
346 *
347 * # Safety
348 *
349 * You must ensure that the relative pointer was successfully set before
350 * calling this function and that the value pointed to does not change it's
351 * offset relative to `RelPtr`
352 *
353 * if relative pointer was never set successfully, this function is UB
354 */
355 #[inline]
356 unsafe fn as_raw_unchecked_impl(&self) -> *const T {
357 nn_to_ptr(T::compose(
358 NonNull::new(self.0.add(self as *const Self as *const u8)),
359 self.1.get()
360 ))
361 }
362
363 /**
364 * Converts the relative pointer into a normal raw pointer
365 *
366 * # Safety
367 *
368 * You must ensure that the relative pointer was successfully set before
369 * calling this function and that the value pointed to does not change it's
370 * offset relative to `RelPtr`
371 *
372 * if relative pointer was never set successfully, this function is UB
373 */
374 #[inline]
375 pub unsafe fn as_raw_unchecked(&mut self) -> *mut T {
376 self.as_raw_unchecked_impl() as _
377 }
378
379 /**
380 * Converts the relative pointer into a normal raw pointer
381 *
382 * # Safety
383 *
384 * Same as `RelPtr::as_raw_unchecked`
385 */
386 #[inline]
387 pub unsafe fn as_non_null_unchecked(&mut self) -> NonNull<T> {
388 T::compose(
389 NonNull::new(self.0.add(self as *mut Self as *mut u8)),
390 self.1.get()
391 ).unchecked_unwrap()
392 }
393
394 /**
395 * Gets a reference from the relative pointer
396 *
397 * # Safety
398 *
399 * Same as `RelPtr::as_raw_unchecked`
400 */
401 #[inline]
402 pub unsafe fn as_ref_unchecked(&self) -> &T {
403 &*self.as_raw_unchecked_impl()
404 }
405
406 /**
407 * Gets a mutable reference from the relative pointer
408 *
409 * # Safety
410 *
411 * Same as `RelPtr::as_raw_unchecked`
412 */
413 #[inline]
414 pub unsafe fn as_mut_unchecked(&mut self) -> &mut T {
415 &mut *self.as_raw_unchecked()
416 }
417}
418
419impl<T: ?Sized + MetaData, I: Nullable> RelPtr<T, I> {
420 /**
421 * Converts the relative pointer into a normal raw pointer
422 *
423 * # Safety
424 *
425 * You must ensure that if the relative pointer was successfully set then
426 * the value pointed to does not change it's offset relative to `RelPtr`
427 *
428 * if the relative pointer was never successfully set `RelPtr::as_non_null` returns None,
429 */
430 #[inline]
431 unsafe fn as_non_null_impl(&self) -> Ptr<T> {
432 if self.is_null() {
433 None
434 } else {
435 T::compose(
436 NonNull::new(self.0.add(self as *const Self as *const u8)),
437 self.1.get()
438 )
439 }
440 }
441
442 /**
443 * Converts the relative pointer into a normal raw pointer
444 *
445 * Note: if `self.is_null()` then a null pointer will be returned
446 *
447 * # Safety
448 *
449 * You must ensure that if the relative pointer was successfully set then
450 * the value pointed to does not change it's offset relative to `RelPtr`
451 *
452 * if the relative pointer was not successfully set `RelPtr::as_raw` returns null,
453 * this function is safe for all types where `size_of::<*mut T>() == size_of::<usize>()`,
454 * otherwise this function is UB
455 */
456 #[inline]
457 pub unsafe fn as_raw(&mut self) -> *mut T {
458 nn_to_ptr(self.as_non_null())
459 }
460
461 /**
462 * Converts the relative pointer into a normal raw pointer
463 *
464 * # Safety
465 *
466 * You must ensure that if the relative pointer was successfully set then
467 * the value pointed to does not change it's offset relative to `RelPtr`
468 *
469 * if the relative pointer was never successfully set `RelPtr::as_non_null` returns None,
470 */
471 #[inline]
472 pub unsafe fn as_non_null(&mut self) -> Ptr<T> {
473 self.as_non_null_impl()
474 }
475
476 /**
477 * Gets a reference from the relative pointer,
478 * if the relative pointer is null, then `None` is
479 * returned
480 *
481 * # Safety
482 *
483 * You are not allows to alias another mutable reference,
484 * as per the aliasing rules of references
485 *
486 * Same as `RelPtr::as_non_null`
487 */
488 #[inline]
489 pub unsafe fn as_ref(&self) -> Option<&T> {
490 Some(&*self.as_non_null_impl()?.as_ptr())
491 }
492
493 /**
494 * Gets a reference from the relative pointer,
495 * if the relative pointer is null, then `None` is
496 * returned
497 *
498 * # Safety
499 *
500 * You are not allows to alias this mutable reference,
501 * as per the aliasing rules of references
502 *
503 * Same as `RelPtr::as_non_null`
504 */
505 #[inline]
506 pub unsafe fn as_mut(&mut self) -> Option<&mut T> {
507 Some(&mut *self.as_non_null()?.as_ptr())
508 }
509}