bitstring_trees/
walk_mut.rs

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
//! Walk tree structures without call stack

use core::{
	marker::PhantomData,
	ptr::NonNull,
};

use alloc::vec::Vec;

/// Allows different node and tree types in [`WalkMut`].
pub enum NodeOrTree<T, N> {
	/// [`WalkMut`] is currently at a node
	Node(N),
	/// [`WalkMut`] is currently at tree
	Tree(T),
}

impl<T, N> NodeOrTree<T, N> {
	/// Map tree value
	pub fn map_tree<F, U>(self, f: F) -> NodeOrTree<U, N>
	where
		F: FnOnce(T) -> U,
	{
		match self {
			Self::Tree(r) => NodeOrTree::Tree(f(r)),
			Self::Node(n) => NodeOrTree::Node(n),
		}
	}

	/// Map node value
	pub fn map_node<F, U>(self, f: F) -> NodeOrTree<T, U>
	where
		F: FnOnce(N) -> U,
	{
		match self {
			Self::Tree(r) => NodeOrTree::Tree(r),
			Self::Node(n) => NodeOrTree::Node(f(n)),
		}
	}

	/// Return node
	pub fn node(self) -> Option<N> {
		match self {
			Self::Tree(_) => None,
			Self::Node(n) => Some(n),
		}
	}
}

impl<N> NodeOrTree<N, N> {
	/// If tree and node type are equivalent extract inner type.
	#[inline]
	pub fn flatten(self) -> N {
		match self {
			Self::Tree(r) => r,
			Self::Node(n) => n,
		}
	}
}

impl<N> NodeOrTree<Option<N>, N> {
	/// If tree and node type are equivalent extract inner type.
	#[inline]
	pub fn flatten_optional(self) -> Option<N> {
		match self {
			Self::Tree(r) => r,
			Self::Node(n) => Some(n),
		}
	}
}

/// Walk tree structures without call stack
///
/// Walking tree structures with mutable references usually
/// requires a recursive call stack to make the borrow-checker
/// happy.
///
/// This uses a stack ([`Vec`]) to keep track of the "current"
/// mutable reference (and hiding the previous ones).
///
/// (There is no way to implement this without `unsafe`, but the
/// abstraction should be safe.)
///
/// Each nested level can also track additional value of type `A`.
pub struct WalkMut<'r, T: ?Sized, N: ?Sized, A = ()> {
	_lifetime: PhantomData<&'r mut T>,
	tree: NonNull<T>,
	stack: Vec<(NonNull<N>, A)>,
}

impl<'r, T: ?Sized, N: ?Sized, A> WalkMut<'r, T, N, A> {
	/// Start a new tree walk at a tree
	pub fn new(tree: &'r mut T) -> Self {
		Self {
			_lifetime: PhantomData,
			tree: tree.into(),
			stack: Vec::new(),
		}
	}

	/// Walk down the tree one step
	///
	/// The step can fail by returning [`Err`].
	pub fn try_walk<F, E>(&mut self, with: F) -> Result<(), E>
	where
		F: for<'n> FnOnce(NodeOrTree<&'n mut T, &'n mut N>) -> Result<(&'n mut N, A), E>,
	{
		match with(self.current_mut()) {
			Err(e) => Err(e),
			Ok((next, add)) => {
				let next: NonNull<N> = next.into();
				self.stack.push((next, add));
				Ok(())
			},
		}
	}

	/// Walk up to the previous level.
	///
	/// Returns the associated data stored with the step,
	/// or [`None`] if already at the initial tree.
	pub fn pop(&mut self) -> Option<A> {
		Some(self.stack.pop()?.1)
	}

	/// Walk up to tree
	pub fn pop_all(&mut self) -> &mut T {
		self.stack.clear();
		unsafe { self.tree.as_mut() }
	}

	/// Get mutable reference to current node or tree
	///
	/// If you need the result to outlive the destruction of the [`WalkMut`] value, see [`into_current_mut`].
	///
	/// [`into_current_mut`]: WalkMut::into_current_mut
	pub fn current_mut(&mut self) -> NodeOrTree<&mut T, &mut N> {
		if let Some((cur, _)) = self.stack.last_mut() {
			NodeOrTree::Node(unsafe { cur.as_mut() })
		} else {
			NodeOrTree::Tree(unsafe { self.tree.as_mut() })
		}
	}

	/// Extract mutable reference to current node or tree
	///
	/// Also see [`current_mut`]
	///
	/// [`current_mut`]: WalkMut::current_mut
	pub fn into_current_mut(mut self) -> NodeOrTree<&'r mut T, &'r mut N> {
		// safety: dropping stack of references means nothing else can create
		// new references to them while 'r still blocks new references to the root.
		if let Some((cur, _)) = self.stack.last_mut() {
			NodeOrTree::Node(unsafe { cur.as_mut() })
		} else {
			NodeOrTree::Tree(unsafe { self.tree.as_mut() })
		}
	}

	/// Extract mutable reference to tree
	pub fn into_tree_mut(mut self) -> &'r mut T {
		self.stack.clear();
		// safety: same as pop_all() + into_current_mut() (which must return the tree)
		unsafe { self.tree.as_mut() }
	}

	/// Get reference to current node or tree
	pub fn current(&self) -> NodeOrTree<&T, &N> {
		if let Some((cur, _)) = self.stack.last() {
			NodeOrTree::Node(unsafe { cur.as_ref() })
		} else {
			NodeOrTree::Tree(unsafe { self.tree.as_ref() })
		}
	}
}