mutcursor/
mut_cursor_vec.rs

1
2use core::ptr::NonNull;
3use core::marker::PhantomData;
4
5/// Similar to [`MutCursor`](crate::MutCursor), but allows for a dynamically growing stack
6///
7/// `MutCursorVec` is not available if the [`alloc`](crate::features#alloc) feature is disabled.
8/// (The feature is enabled by default.)
9pub struct MutCursorVec<'root, T: ?Sized + 'root> {
10    top: NonNull<T>,
11    stack: alloc::vec::Vec<NonNull<T>>,
12    phantom: PhantomData<&'root mut T>, //Variance
13}
14
15unsafe impl<'a, T> Sync for MutCursorVec<'a, T> where T: Sync, T: ?Sized {}
16unsafe impl<'a, T> Send for MutCursorVec<'a, T> where T: Send, T: ?Sized {}
17
18impl<'root, T: ?Sized + 'root> MutCursorVec<'root, T> {
19    /// Returns a new `MutCursorVec` with a reference to the specified root
20    #[inline]
21    pub fn new(root: &'root mut T) -> Self {
22        Self {
23            top: root.into(),
24            stack: alloc::vec::Vec::new(),
25            phantom: PhantomData::default(),
26        }
27    }
28    /// Returns a new `MutCursorVec` with a reference to the specified root, and an allocated buffer
29    /// for `capacity` references
30    #[inline]
31    pub fn new_with_capacity(root: &'root mut T, capacity: usize) -> Self {
32        Self {
33            top: root.into(),
34            stack: alloc::vec::Vec::with_capacity(capacity),
35            phantom: PhantomData::default(),
36        }
37    }
38    /// Returns a const reference from the mutable reference on the top of the stack
39    #[inline]
40    pub fn top(&self) -> &T {
41        unsafe{ self.top.as_ref() }
42    }
43    /// Returns the mutable reference on the top of the stack 
44    #[inline]
45    pub fn top_mut(&mut self) -> &mut T {
46        unsafe{ self.top.as_mut() }
47    }
48    /// Returns the mutable reference on the top of the stack, consuming the stack
49    #[inline]
50    pub fn into_mut(mut self) -> &'root mut T {
51        unsafe{ self.top.as_mut() }
52    }
53    /// Consumes the stack and returns a mutable reference to an object with the `'root` lifetime,
54    /// if a closure returns `Ok`, otherwise returns the stack and a custom error value
55    ///
56    /// NOTE: Usage is identical to [MutCursor::try_map_into_mut](crate::MutCursor::try_map_into_mut)
57    #[inline]
58    pub fn try_map_into_mut<U, E, F>(mut self, f: F) -> Result<&'root mut U, (Self, E)>
59        where for<'r> F: FnOnce(&'r mut T) -> Result<&'r mut U, E>
60    {
61        let top_ref = unsafe{ self.top_mut_internal() };
62        match f(top_ref) {
63            Ok(r) => Ok(r),
64            Err(e) => Err((self, e))
65        }
66    }
67    /// Returns the number of excess references stored in the stack, which corresponds to the number of
68    /// times [`backtrack`](Self::backtrack) may be called
69    #[inline]
70    pub fn depth(&self) -> usize {
71        self.stack.len()
72    }
73    /// Returns the number of references the stack is capable of holding without reallocation
74    #[inline]
75    pub fn capacity(&self) -> usize {
76        self.stack.capacity() + 1
77    }
78    /// Steps deeper into the traversal, pushing a new reference onto the top of the stack
79    ///
80    /// If the `step_f` closure returns `Some()`, the contained reference is pushed onto the stack and
81    /// this method returns `true`.  If the closure returns `None` then the stack is unmodified and this
82    /// method returns `false`.
83    #[inline]
84    pub fn advance<F>(&mut self, step_f: F) -> bool
85        where F: FnOnce(&mut T) -> Option<&mut T>
86    {
87        match step_f(unsafe{ self.top_mut_internal() }) {
88            Some(new_node) => {
89                unsafe{ self.push(new_node); }
90                true
91            },
92            None => false
93        }
94    }
95    /// Pops a reference from the stack, exposing the prior reference as the new [`top`](Self::top)
96    ///
97    /// This method will panic if the stack contains only 1 entry
98    #[inline]
99    pub fn backtrack(&mut self) {
100        match self.stack.pop() {
101            Some(top_ptr) => {
102                self.top = top_ptr;
103            },
104            None => panic!("MutCursor must contain valid reference")
105        }
106    }
107    /// Pops all references from the stack, exposing the root reference as the [`top`](Self::top)
108    ///
109    /// This method does nothing if the stack is already at the root
110    #[inline]
111    pub fn to_root(&mut self) {
112        if self.stack.len() > 0 {
113            self.stack.truncate(1);
114            self.top = self.stack.pop().unwrap();
115        }
116    }
117    /// Private
118    #[inline]
119    unsafe fn top_mut_internal(&mut self) -> &'root mut T {
120        unsafe{ self.top.as_mut() }
121    }
122    /// Private
123    #[inline]
124    unsafe fn push(&mut self, t_ref: &'root mut T) {
125        let mut top_ptr: NonNull<T> = t_ref.into();
126        core::mem::swap(&mut top_ptr, &mut self.top);
127        self.stack.push(top_ptr);
128    }
129}
130
131impl<'root, T: ?Sized> core::ops::Deref for MutCursorVec<'root, T> {
132    type Target = T;
133    fn deref(&self) -> &T {
134        self.top()
135    }
136}
137
138impl<'root, T: ?Sized> core::ops::DerefMut for MutCursorVec<'root, T> {
139    fn deref_mut(&mut self) -> &mut T {
140        self.top_mut()
141    }
142}
143
144#[cfg(test)]
145mod test {
146    use std::*;
147    use std::boxed::*;
148
149    use crate::*;
150
151    struct TreeNode {
152        val: usize,
153        next: Option<Box<TreeNode>>
154    }
155    impl TreeNode {
156        fn new(count: usize) -> Self {
157            if count > 0 {
158                Self {val: count, next: Some(Box::new(Self::new(count-1)))}
159            } else {
160                Self {val: 0, next: None}
161            }
162        }
163        fn traverse(&mut self) -> Option<&mut Self> {
164            self.next.as_mut().map(|boxed| &mut **boxed)
165        }
166    }
167
168    #[test]
169    fn basics_vec() {
170        let mut tree = TreeNode::new(10);
171        let mut node_stack = MutCursorVec::<TreeNode>::new(&mut tree);
172
173        while node_stack.advance(|node| {
174            node.traverse()
175        }) {}
176
177        assert_eq!(node_stack.top().val, 0);
178        assert_eq!(node_stack.depth(), 10);
179
180        node_stack.backtrack();
181        assert_eq!(node_stack.top().val, 1);
182        assert_eq!(node_stack.depth(), 9);
183
184        node_stack.backtrack();
185        node_stack.backtrack();
186        node_stack.backtrack();
187        assert_eq!(node_stack.top().val, 4);
188        assert_eq!(node_stack.depth(), 6);
189
190        while node_stack.advance(|node| {
191            node.traverse()
192        }) {}
193        assert_eq!(node_stack.top().val, 0);
194        assert_eq!(node_stack.depth(), 10);
195
196        node_stack.backtrack();
197        node_stack.backtrack();
198        node_stack.backtrack();
199        node_stack.backtrack();
200        node_stack.backtrack();
201        node_stack.backtrack();
202        assert_eq!(node_stack.top().val, 6);
203        assert_eq!(node_stack.depth(), 4);
204
205        assert_eq!(node_stack.into_mut().val, 6);
206    }
207
208    /// See https://github.com/luketpeterson/mutcursor/issues/1#issuecomment-2549242493
209    #[test]
210    fn miri_tagging_issue() {
211        let x = &mut 0;
212        let mut c = MutCursorVec::new(x);
213        c.advance(|x| Some(x));
214        c.backtrack();
215        println!("{}", c.top());
216    }
217}
mutcursor/mut_cursor_vec.rs

mutcursor/
mut_cursor_vec.rs
