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