recursive_reference/lib.rs
1//! Recursive reference.
2//!
3//!This crate provides a way to traverse recursive structures easily and safely.
4//!Rust's lifetime rules will usually force you to either only walk forward through the structure,
5//!or use recursion, calling your method recursively every time you go down a node,
6//!and returning every time you want to go back up, which leads to terrible code.
7//!
8//!Instead, you can use the [`RecRef`] type, to safely and dynamically walk up
9//!and down your recursive structure.
10//!
11//!# Examples
12//!
13//! Say we have a recursive linked list structure
14//! ----------------------------------------------
15//!```rust
16//!enum List<T> {
17//! Root(Box<Node<T>>),
18//! Empty,
19//!}
20//!struct Node<T> {
21//! value: T,
22//! next: List<T>,
23//!}
24//!```
25//!
26//!We can use a [`RecRef`] directly
27//!----------------------------------------------
28//!```rust
29//!use recursive_reference::*;
30//!
31//! # enum List<T> {
32//! # Root(Box<Node<T>>),
33//! # Empty,
34//! # }
35//! # struct Node<T> {
36//! # value: T,
37//! # next: List<T>,
38//! # }
39//!
40//!fn main() -> Result<(), ()> {
41//! // crate a list to test
42//! let node1 = Node {
43//! value: 5,
44//! next: List::Empty,
45//! };
46//! let mut node2 = Node {
47//! value: 2,
48//! next: List::Root(Box::new(node1)),
49//! };
50//!
51//! // create a `RecRef`
52//! let mut rec_ref = RecRef::new(&mut node2);
53//! // rec_ref is a smart pointer to the current node
54//! assert_eq!(rec_ref.value, 2);
55//!
56//! // move forward through the list
57//! RecRef::extend_result(&mut rec_ref, |node| match &mut node.next {
58//! List::Root(next_node) => Ok(next_node),
59//! List::Empty => Err(()),
60//! })?;
61//! assert_eq!(rec_ref.value, 5); // now we're at the second node
62//!
63//! // pop the `RecRef`, moving it back to the head
64//! RecRef::pop(&mut rec_ref).ok_or(())?;
65//! assert_eq!(rec_ref.value, 2);
66//! Ok(())
67//!}
68//!```
69//!
70//!We can also wrap a [`RecRef`] in a walker struct
71//!----------------------------------------------
72//!Note: this time we are using a `RecRef<List<T>>` and not a `RecRef<Node<T>>`, to allow pointing
73//!at the empty end of the list.
74//!```rust
75//!use recursive_reference::*;
76//! # enum List<T> {
77//! # Root(Box<Node<T>>),
78//! # Empty,
79//! # }
80//! # struct Node<T> {
81//! # value: T,
82//! # next: List<T>,
83//! # }
84//!struct Walker<'a, T> {
85//! rec_ref: RecRef<'a, Node<T>>,
86//!}
87//!impl<'a, T> Walker<'a, T> {
88//! /// Crates a new Walker
89//! pub fn new(node: &'a mut Node<T>) -> Self {
90//! Walker {
91//! rec_ref: RecRef::new(node),
92//! }
93//! }
94//!
95//! /// Returns `None` when at the tail end of the list.
96//! /// Moves to the next node.
97//! pub fn next(&mut self) -> Option<()> {
98//! RecRef::extend_result(&mut self.rec_ref, |current| match &mut current.next {
99//! List::Empty => Err(()),
100//! List::Root(node) => Ok(node),
101//! })
102//! .ok()
103//! }
104//!
105//! /// Returns `None` when at the head of the list.
106//! /// Goes back to the previous node.
107//! pub fn prev(&mut self) -> Option<()> {
108//! RecRef::pop(&mut self.rec_ref)?;
109//! Some(())
110//! }
111//!
112//! /// Returns `None` when at the tail end of the list.
113//! /// Returns `Some(reference)` where `reference` is a mutqable reference to the current value.
114//! pub fn value_mut(&mut self) -> &mut T {
115//! &mut self.rec_ref.value
116//! }
117//!}
118//!
119//!fn main() -> Result<(), ()> {
120//! // crate a list to test
121//! let node1 = Node {
122//! value: 5,
123//! next: List::Empty,
124//! };
125//! let mut node2 = Node {
126//! value: 2,
127//! next: List::Root(Box::new(node1)),
128//! };
129//!
130//! // create a walker for the list
131//! let mut walker = Walker::new(&mut node2);
132//! // walker has mutable access to the node value
133//! assert_eq!(*walker.value_mut(), 2);
134//! // move to the next node
135//! walker.next().ok_or(())?;
136//! assert_eq!(*walker.value_mut(), 5);
137//! assert_eq!(walker.next(), None); // currently at the end of the list
138//! // move back
139//! walker.prev().ok_or(())?;
140//! assert_eq!(*walker.value_mut(), 2);
141//! Ok(())
142//!}
143//!```
144//! With a [`RecRef`] you can
145//! ----------------------------------------------
146//! * Use the current reference (i.e, the top reference).
147//! the [`RecRef`] is a smart pointer to it.
148//! * Freeze the current reference
149//! and extend the [`RecRef`] with a new reference derived from it, using [`extend`][RecRef::extend] and similar functions.
150//! for example, push to the stack a reference to the child of the current node.
151//! * Pop the stack to get back to the previous reference, unfreezing it.
152//!
153//! # Safety
154//! The [`RecRef`] type is implemented using unsafe rust, but provides a safe interface.
155//! The [`RecRef`] methods' types guarantee that the references will always have a legal lifetime
156//! and will respect rust's borrow rules, even if that lifetime is not known in advance.
157//!
158//! The [`RecRef`] obeys rust's borrowing rules, by simulating freezing. Whenever
159//! you extend a [`RecRef`] with a reference `child_ref` that is derived from the current
160//! reference `parent_ref`, the [`RecRef`] freezes `parent_ref`, and no longer allows
161//! `parent_ref` to be used.
162//! When `child_ref` will be popped from the [`RecRef`],
163//! `parent_ref` will be allowed to be used again.
164//!
165//! This is essentially the same as what would have happened if you wrote your functions recursively,
166//! but it's decoupled from the actual call stack.
167//!
168//! Another important point to consider is the safety of
169//! the actual call to [`extend`][RecRef::extend]: see its documentation.
170#![no_std]
171#![doc(html_root_url = "https://docs.rs/recursive_reference/0.3.0/recursive_reference/")]
172
173extern crate alloc;
174use alloc::vec::*;
175
176use core::marker::PhantomData;
177use core::ops::{Deref, DerefMut};
178use core::ptr::NonNull;
179use void::ResultVoidExt;
180
181/// A Recursive reference.
182/// This struct is used to allow recursively reborrowing mutable references in a dynamic
183/// but safe way.
184///
185/// `RecRef<'a, T>` represents a reference to a value of type `T`, with lifetime `'a`,
186/// which can move recursively into and out of its subfields of the same type `T`.
187///
188/// With a [`RecRef`] you can
189/// ----------------------------------------------
190/// * Use the current reference (i.e, the top reference).
191/// the [`RecRef`] is a smart pointer to it.
192/// * Freeze the current reference
193/// and extend the [`RecRef`] with a new reference derived from it, using [`extend`][RecRef::extend] and similar functions.
194/// for example, push to the stack a reference to the child of the current node.
195/// * Pop the stack to get back to the previous reference, unfreezing it.
196///
197/// The methods' types guarantee that the references will always have a legal lifetime
198/// and will respect rust's borrow rules, even if that lifetime is not known in advance.
199///
200/// Internally, the [`RecRef`] stores a [`Vec`] of pointers, that it extends and pops from.
201pub struct RecRef<'a, T: ?Sized> {
202 head: NonNull<T>,
203 vec: Vec<NonNull<T>>,
204 phantom: PhantomData<&'a mut T>,
205}
206
207impl<'a, T: ?Sized> RecRef<'a, T> {
208 /// Creates a new RecRef containing only a single reference.
209 pub fn new(r: &'a mut T) -> Self {
210 RecRef {
211 head: NonNull::from(r),
212 vec: Vec::new(),
213 phantom: PhantomData,
214 }
215 }
216
217 /// Returns the size of `rec_ref`, i.e, the amount of references in it.
218 /// It increases every time you extend `rec_ref`, and decreases every time you pop
219 /// `rec_ref`.
220 /// The size of a new [`RecRef`] is always `1`.
221 pub fn size(rec_ref: &Self) -> usize {
222 rec_ref.vec.len() + 1
223 }
224
225 /// This function extends `rec_ref` one time. If the current
226 /// reference is `current_ref: &mut T`, then this call extends `rec_ref`
227 /// with the new reference `ref2: &mut T = func(current_ref)`.
228 /// After this call, `rec_ref` will expose the new `ref2`, and `current_ref`
229 /// will be frozen (As it is borrowed by `ref2`), until `ref2` is
230 /// popped off, unfreezing `current_ref`.
231 ///
232 /// # Safety:
233 /// Pay close attention to the type of `func`: we require that
234 /// `F: for<'b> FnOnce(&'b mut T) -> &'b mut T`. That is, for every lifetime `'b`,
235 /// we require that `F: FnOnce(&'b mut T) -> &'b mut T`.
236 ///
237 /// Let's define `'freeze_time` to be the time `ref2` will be in the [`RecRef`].
238 /// That is, `'freeze_time`
239 /// is the time for which `ref2` will live, and the lifetime in which `current_ref`
240 /// will be frozen by `ref2`. Then, the type of `func` should have been
241 /// `FnOnce(&'freeze_time mut T) -> &'freeze_time mut T`. If that woudld have been the type
242 /// of `func`, the code would've followed rust's borrowing rules correctly.
243 ///
244 /// However, we can't know yet what that
245 /// lifetime is: it will be whatever amount of time passes until the programmer decides
246 /// to pop `ref2` out of the [`RecRef`]. And that hasn't even been decided at this point.
247 /// Whatever lifetime `'freeze_time` that turns out to be, we will know
248 /// after-the-fact that the type of `func` should have been
249 /// `FnOnce(&'freeze_time mut T) -> &'freeze_time mut T`.
250 ///
251 /// Therefore, the solution is to require that `func` will be able to work with any value of
252 /// `'freeze_time`. Then we can be
253 /// sure that the code would've worked correctly if we put the correct lifetime there.
254 /// Therefore, we can always pick correct lifetimes after-the-fact, so the code must be safe.
255 ///
256 /// Also note:
257 /// The type ensures that the current reference can't be leaked outside of `func`.
258 /// `func` can't guarantee that
259 /// `current_ref` will live for any length of time, so it can't store it outside anywhere
260 /// or give it to anything.
261 /// It can only use `current_ref` while still inside `func`,
262 /// and use it in order to return `ref2`, which is the
263 /// intended usage.
264 pub fn extend<F>(rec_ref: &mut Self, func: F)
265 where
266 F: for<'b> FnOnce(&'b mut T) -> &'b mut T,
267 {
268 Self::extend_result(rec_ref, |r| Ok(func(r))).void_unwrap()
269 }
270
271 /// Same as [`Self::extend`], but allows the function to return an error value.
272 pub fn extend_result<E, F>(rec_ref: &mut Self, func: F) -> Result<(), E>
273 where
274 F: for<'b> FnOnce(&'b mut T) -> Result<&'b mut T, E>,
275 {
276 Self::extend_result_precise(rec_ref, |r, _phantom| func(r))
277 }
278
279 /// Same as [`Self::extend`], but allows the function to return an error value,
280 /// and also tells the inner function that `'a : 'b` using a phantom argument.
281 pub fn extend_result_precise<E, F>(rec_ref: &mut Self, func: F) -> Result<(), E>
282 where
283 F: for<'b> FnOnce(&'b mut T, PhantomData<&'b &'a ()>) -> Result<&'b mut T, E>,
284 {
285 // The compiler is told explicitly that the lifetime is `'a`.
286 // Otherwise the minimal lifetime possible is chosen.
287 // It probably doesn't matter, since we specifically require `func` to be able to work
288 // with any lifetime, and the references are converted to pointers immediately.
289 // However, that is the "most correct" lifetime - the reference's actual lifetime may
290 // be anything up to `'a`,
291 // depending on whether the user will pop it earlier than that.
292 let head_ref: &'a mut T = unsafe { rec_ref.head.as_mut() };
293
294 match func(head_ref, PhantomData) {
295 Ok(p) => {
296 Self::push(rec_ref, p);
297 Ok(())
298 }
299 Err(e) => Err(e),
300 }
301 }
302
303 /// This function maps the top of the [`RecRef`]. It's similar to [`Self::extend`], but
304 /// it replaces the current reference instead of keeping it. See [`Self::extend`] for more details.
305 pub fn map<F>(rec_ref: &mut Self, func: F)
306 where
307 F: for<'b> FnOnce(&'b mut T) -> &'b mut T,
308 {
309 Self::map_result(rec_ref, |r| Ok(func(r))).void_unwrap()
310 }
311
312 /// Same as [`Self::map`], but allows the function to return an error value.
313 pub fn map_result<E, F>(rec_ref: &mut Self, func: F) -> Result<(), E>
314 where
315 F: for<'b> FnOnce(&'b mut T) -> Result<&'b mut T, E>,
316 {
317 Self::map_result_precise(rec_ref, |r, _| func(r))
318 }
319
320 /// Same as [`Self::map`], but allows the function to return an error value,
321 /// and also tells the inner function that `'a : 'b` using a phantom argument.
322 pub fn map_result_precise<E, F>(rec_ref: &mut Self, func: F) -> Result<(), E>
323 where
324 F: for<'b> FnOnce(&'b mut T, PhantomData<&'b &'a ()>) -> Result<&'b mut T, E>,
325 {
326 // The compiler is told explicitly that the lifetime is `'a`.
327 // Otherwise the minimal lifetime possible is chosen.
328 // It probably doesn't matter, since we specifically require `func` to be able to work
329 // with any lifetime, and the references are converted to pointers immediately.
330 // However, that is the "most correct" lifetime - the reference's actual lifetime may
331 // be anything up to `'a`,
332 // depending on whether the user will pop it earlier than that.
333 let head_ref: &'a mut T = unsafe { rec_ref.head.as_mut() };
334
335 match func(head_ref, PhantomData) {
336 Ok(p) => {
337 rec_ref.head = NonNull::from(p);
338 Ok(())
339 }
340 Err(e) => Err(e),
341 }
342 }
343
344 /// Push another reference to the [`RecRef`], unrelated to the current one.
345 /// `rec_ref.push(new_ref)` is morally equivalent to `rec_ref.extend_result_precise(move |_, _| { Ok(new_ref) })`.
346 /// However, you might have some trouble making the anonymous function conform to the
347 /// right type.
348 pub fn push(rec_ref: &mut Self, r: &'a mut T) {
349 rec_ref.vec.push(rec_ref.head);
350 rec_ref.head = NonNull::from(r);
351
352 /* alternative definition using a call to `extend_result_precise`.
353 // in order to name 'x, replace the signature with:
354 // pub fn push<'x>(rec_ref: &'x mut Self, r : &'a mut T) {
355 // this is used in order to tell the closure to conform to the right type
356 fn helper<'a,'x, T : ?Sized, F> (f : F) -> F where
357 F : for<'b> FnOnce(&'b mut T, PhantomData<&'b &'a ()>)
358 -> Result<&'b mut T, void::Void> + 'x
359 { f }
360
361 Self::extend_result_precise(rec_ref,
362 helper::<'a,'x>(move |_, _phantom| { Ok(r) })
363 ).void_unwrap();
364 */
365 }
366
367 /// Lets the user use the last reference for some time, and discards it completely.
368 /// After the user uses it, the next time they inspect the [`RecRef`], it won't be there.
369 /// If the [`RecRef`] has only one reference left, this returns `None`, because
370 /// the [`RecRef`] can't be empty.
371 pub fn pop(rec_ref: &mut Self) -> Option<&mut T> {
372 let res = unsafe { rec_ref.head.as_mut() };
373 rec_ref.head = rec_ref.vec.pop()?; // We can't pop the original reference. In that case, Return None.
374 Some(res)
375 }
376
377 /// Discards the [`RecRef`] and returns the last reference.
378 /// The difference between this and using [`Self::pop`] are:
379 /// * This will consume the [`RecRef`]
380 /// * [`Self::pop`] will never pop the first original reference, because that would produce an
381 /// invalid [`RecRef`]. [`Self::into_ref`] will.
382 pub fn into_ref(mut rec_ref: Self) -> &'a mut T {
383 unsafe { rec_ref.head.as_mut() }
384 }
385}
386
387/// [`RecRef<T>`] represents a reference to a value of type `T`,
388/// which can move recursively into and out of its subfields of the same type `T`.
389/// Therefore, it implements `Deref` and `DerefMut` with `Item=T`.
390impl<'a, T: ?Sized> Deref for RecRef<'a, T> {
391 type Target = T;
392 fn deref(&self) -> &T {
393 unsafe { self.head.as_ref() }
394 }
395}
396
397/// [`RecRef<T>`] represents a reference to a value of type `T`,
398/// which can move recursively into and out of its subfields of the same type `T`.
399/// Therefore, it implements `Deref` and `DerefMut` with `Item=T`.
400impl<'a, T: ?Sized> DerefMut for RecRef<'a, T> {
401 fn deref_mut(&mut self) -> &mut T {
402 unsafe { self.head.as_mut() }
403 }
404}
405
406impl<'a, Q: ?Sized, T: ?Sized + AsRef<Q>> AsRef<Q> for RecRef<'a, T> {
407 fn as_ref(&self) -> &Q {
408 AsRef::as_ref(&**self)
409 }
410}
411
412impl<'a, Q: ?Sized, T: ?Sized + AsMut<Q>> AsMut<Q> for RecRef<'a, T> {
413 fn as_mut(&mut self) -> &mut Q {
414 AsMut::as_mut(&mut **self)
415 }
416}
417
418impl<'a, T: ?Sized> From<&'a mut T> for RecRef<'a, T> {
419 fn from(r: &'a mut T) -> Self {
420 Self::new(r)
421 }
422}
423
424/// # Safety:
425/// Behaviorally, A [`RecRef`] is the same as `&'a mut T`, and
426/// should be [`Send`] for the same reason. Additionally, it contains a [`Vec`].
427/// The [`Send`] instance for [`Vec`] contains the bound `A: Send` for the allocator type `A`,
428/// so we should require that as well. However, we don't have direct access to the
429/// default allocator type. So instead we require `Vec<&'a mut T>: Send`.
430unsafe impl<'a, T: ?Sized + Send> Send for RecRef<'a, T> where Vec<&'a mut T>: Send {}
431
432/// # Safety:
433/// Behaviorally, A [`RecRef`] is the same as `&'a mut T`, and
434/// should be [`Sync`] for the same reason. Additionally, it contains a [`Vec`].
435/// The [`Sync`] instance for [`Vec`] contains the bound `A: Sync` for the allocator type `A`,
436/// so we should require that as well. However, we don't have direct access to the
437/// default allocator type. So instead we require `Vec<&'a mut T>: Sync`.
438unsafe impl<'a, T: ?Sized + Sync> Sync for RecRef<'a, T> where Vec<&'a mut T>: Sync {}