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
//! Recursive reference //! This module provides a way to walk on 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. //! //! Say we have a recursive linked list structure: //!``` //!enum List<T> { //! Root(Box<Node<T>>), //! Empty, //!} //!struct Node<T> { //! value: T, //! next: List<T>, //!} //!``` //! Then we can wrap the RecRef in a struct allowing us to walk up and down //! our list: //!``` //! # enum List<T> { //! # Root(Box<Node<T>>), //! # Empty, //! # } //! # struct Node<T> { //! # value: T, //! # next: List<T>, //! # } //! use recursive_reference::*; //! struct Walker<'a, T> { //! rec_ref : RecRef<'a, List<T>> //! } //! impl<'a, T> Walker<'a, T> { //! pub fn new(list: &'a mut List<T>) -> Self { //! Walker { //! rec_ref : RecRef::new(list) //! } //! } //! //! /// Returns `None` when at the tail end of the list //! pub fn next(&mut self) -> Option<()> { //! self.rec_ref.extend_result(|current| match current { //! List::Empty => Err(()), //! List::Root(node) => Ok(&mut node.next), //! }).ok() //! } //! //! /// Returns `None` when at the head of the list //! pub fn prev(&mut self) -> Option<()> { //! self.rec_ref.pop()?; //! Some(()) //! } //! //! /// Returns `None` when at the tail end of the list //! pub fn value_mut(&mut self) -> Option<&mut T> { //! match &mut *self.rec_ref { //! List::Root(node) => Some(&mut node.value), //! List::Empty => None, //! } //! } //! } //! //! fn main() { //! let node1 = Node { value : 5, next : List::Empty }; //! let node2 = Node { value : 2, next : List::Root(Box::new(node1)) }; //! let mut list = List::Root(Box::new(node2)); //! //! let mut walker = Walker::new(&mut list); //! assert_eq!(walker.value_mut().cloned(), Some(2)); //! *walker.value_mut().unwrap() = 7; //! walker.next().unwrap(); //! assert_eq!(walker.value_mut().cloned(), Some(5)); //! walker.next().unwrap(); //! assert_eq!(walker.value_mut().cloned(), None); // end of the list //! walker.prev().unwrap(); //! assert_eq!(walker.value_mut().cloned(), Some(5)); //! walker.prev().unwrap(); //! assert_eq!(walker.value_mut().cloned(), Some(7)); // we changed the value at the head //! } //!``` //! This works by having a stack of references in the RecRef. You can do these toperations: //! * You can always use the current reference. //! that is, the current reference - the RecRef is a smart pointer to it. //! * using [`extend`][RecRef::extend], freeze the current reference //! and extend the RecRef with a new reference derived from it. //! for example, pushing to the stack the child of the current node. //! * pop the stack to get back to the previous references, unfreezing them. //! //! # Safety //! The RecRef type is implemented using unsafe rust, but provides a safe interface. //! //! The RecRef obeys rust's borrowing rules, by simulating freezing. Whenever //! you extend the 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 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. //! //! Internally, the RecRef keeps a stack of pointers, instead of reference, in order not //! to violate rust's invariants. use std::marker::PhantomData; use std::ops::Deref; use std::ops::DerefMut; use void::ResultVoidExt; // TODO: switch to `NonNull` when rust 1.53 arrives. /// A Recursive reference. /// This struct is used to allow recursively reborrowing mutable references in a dynamic /// but safe way. pub struct RecRef<'a, T: ?Sized> { head: *mut T, vec: Vec<*mut T>, phantom: PhantomData<&'a mut T>, } // TODO: consider converting the pointers to values without checking for null values. // it's supposed to work, since the pointers only ever come from references. // these aren't ever supposed to happen. but since we touch unsafe code, we might as well // have clear error message when we `expect()` pub const NO_VALUE_ERROR: &str = "invariant violated: RecRef can't be empty"; pub const NULL_POINTER_ERROR: &str = "error! somehow got null pointer"; impl<'a, T: ?Sized> RecRef<'a, T> { pub fn new(r: &'a mut T) -> Self { RecRef { head: r as *mut T, vec: vec![], phantom: PhantomData, } } pub fn size(&self) -> usize { self.vec.len() + 1 } /// This function extends the RecRef one time. That means, if the current /// reference is `current_ref: &mut T`, then this call extends the RecRef /// with the new reference `ref2: &mut T = func(current_ref)`. /// After this call, the RecRef 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: /// The type ensures no leaking is possible, since `func` can't guarantee that /// `current_ref` will live for any length of time, so it can't leak it anywhere. /// It can only use `current_ref` inside the function, and use it in order to return `ref2`, which is the /// intended usage. /// /// A different point of view is this: we have to borrow `current_ref` to `func` /// with the actual correct lifetime: the lifetime in which it is allowed to /// freeze `current_ref` in order to use `ref2`. /// /// However, we don't know yet what that /// lifetime is: it will be whatever amount of time passes until `ref2` will be /// popped back, unfreezing `current_ref`. (and that lifetime can even be decided dynamically). /// Whatever lifetime `'freeze_time` that turns out to be, the type of `func` should have been /// `func: FnOnce(&'freeze_time mut T) -> &'freeze_time mut T`. /// /// Therefore, we require that `func` will be able to work with any value of `'freeze_time`, so we /// are sure that the code would've worked correctly if we put the correct lifetime there. /// So that ensures the code is safe. /// /// Another point of view is considering what other types we could have given to this function: /// If the type was just /// ```rust,ignore /// fn extend<'a, F : FnOnce(&'a mut T) -> &'a mut T>(&mut self, func : F) /// ``` /// then this function would be unsafe, /// because `func` could leak the reference outside, and then the caller could immediately /// pop the RecRef to get another copy of the same reference. /// /// We could use /// ```rust,ignore /// fn extend<'a, F : FnOnce(&'a mut T) -> &'a mut T>(&'a mut self, func : F) /// ``` /// /// But that would invalidate the whole point of using the RecRef - You couldn't /// use it after extending even once, and it couldn't be any better than a regular mutable reference. pub fn extend<F>(&mut self, func: F) where F: for<'b> FnOnce(&'b mut T) -> &'b mut T, { self.extend_result(|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>(&mut self, func: F) -> Result<(), E> where F: for<'b> FnOnce(&'b mut T) -> Result<&'b mut T, E>, { self.extend_result_precise(|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>(&mut self, func: F) -> Result<(), E> where F: for<'b> FnOnce(&'b mut T, PhantomData<&'b &'a ()>) -> Result<&'b mut T, E>, { // The compiler has to be told explicitly that the lifetime is `'a`. // Otherwise the lifetime is left unconstrained. // It probably doesn't matter much in practice, 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 - its 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 { self.head.as_mut() }.expect(NULL_POINTER_ERROR); match func(head_ref, PhantomData) { Ok(p) => { self.push(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>(&mut self, func: F) where F: for<'b> FnOnce(&'b mut T) -> &'b mut T, { self.map_result(|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>(&mut self, func: F) -> Result<(), E> where F: for<'b> FnOnce(&'b mut T) -> Result<&'b mut T, E>, { self.map_result_precise(|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>(&mut self, func: F) -> Result<(), E> where F: for<'b> FnOnce(&'b mut T, PhantomData<&'b &'a ()>) -> Result<&'b mut T, E>, { // The compiler has to be told explicitly that the lifetime is `'a`. // Otherwise the lifetime is left unconstrained. // It probably doesn't matter much in practice, 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 - its 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 { self.head.as_mut() }.expect(NULL_POINTER_ERROR); match func(head_ref, PhantomData) { Ok(p) => { self.head = p as *mut T; 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(&mut self, r: &'a mut T) { self.vec.push(self.head); self.head = r as *mut T; /* alternative definition using a call to `self.extend_result_precise`. // in order to name 'x, replace the signature with: // pub fn push<'x>(&'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( 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. /// Can't pop the last reference, as the RecRef can't be empty, and returns `None` instead. pub fn pop(&mut self) -> Option<&mut T> { let res = unsafe { self.head.as_mut() }.expect(NULL_POINTER_ERROR); self.head = self.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(self) -> &'a mut T { unsafe { self.head.as_mut() }.expect(NULL_POINTER_ERROR) } /// Gets the [`std::ptr::NonNull`] pointer that is i'th from the top of the RecRef. /// The intended usage is for using the pointers as the inputs to `ptr_eq`. /// However, using the pointers themselves (which requires `unsafe`) will almost definitely /// break rust's guarantees. pub fn get_nonnull(&self, i: usize) -> std::ptr::NonNull<T> { let ptr = if i == 0 { self.head } else { self.vec[self.vec.len() - i] }; std::ptr::NonNull::new(ptr).expect(NULL_POINTER_ERROR) } } impl<'a, T: ?Sized> Deref for RecRef<'a, T> { type Target = T; fn deref(&self) -> &T { unsafe { self.head.as_ref() }.expect(NULL_POINTER_ERROR) } } impl<'a, T: ?Sized> DerefMut for RecRef<'a, T> { fn deref_mut(&mut self) -> &mut T { unsafe { self.head.as_mut() }.expect(NULL_POINTER_ERROR) } } impl<'a, T: ?Sized> From<&'a mut T> for RecRef<'a, T> { fn from(r: &'a mut T) -> Self { Self::new(r) } }