Show More
@@ -43,6 +43,13 b' struct Node {' | |||
|
43 | 43 | children: ChildNodes, |
|
44 | 44 | } |
|
45 | 45 | |
|
46 | /// `(full_path, entry, copy_source)` | |
|
47 | type NodeDataMut<'a> = ( | |
|
48 | &'a WithBasename<HgPathBuf>, | |
|
49 | &'a mut Option<DirstateEntry>, | |
|
50 | &'a mut Option<HgPathBuf>, | |
|
51 | ); | |
|
52 | ||
|
46 | 53 | impl DirstateMap { |
|
47 | 54 | pub fn new() -> Self { |
|
48 | 55 | Self { |
@@ -95,6 +102,87 b' impl DirstateMap {' | |||
|
95 | 102 | } |
|
96 | 103 | } |
|
97 | 104 | } |
|
105 | ||
|
106 | fn iter_nodes<'a>( | |
|
107 | &'a self, | |
|
108 | ) -> impl Iterator<Item = (&'a WithBasename<HgPathBuf>, &'a Node)> + 'a | |
|
109 | { | |
|
110 | // Depth first tree traversal. | |
|
111 | // | |
|
112 | // If we could afford internal iteration and recursion, | |
|
113 | // this would look like: | |
|
114 | // | |
|
115 | // ``` | |
|
116 | // fn traverse_children( | |
|
117 | // children: &ChildNodes, | |
|
118 | // each: &mut impl FnMut(&Node), | |
|
119 | // ) { | |
|
120 | // for child in children.values() { | |
|
121 | // traverse_children(&child.children, each); | |
|
122 | // each(child); | |
|
123 | // } | |
|
124 | // } | |
|
125 | // ``` | |
|
126 | // | |
|
127 | // However we want an external iterator and therefore can’t use the | |
|
128 | // call stack. Use an explicit stack instead: | |
|
129 | let mut stack = Vec::new(); | |
|
130 | let mut iter = self.root.iter(); | |
|
131 | std::iter::from_fn(move || { | |
|
132 | while let Some((key, child_node)) = iter.next() { | |
|
133 | // Pseudo-recursion | |
|
134 | let new_iter = child_node.children.iter(); | |
|
135 | let old_iter = std::mem::replace(&mut iter, new_iter); | |
|
136 | stack.push((key, child_node, old_iter)); | |
|
137 | } | |
|
138 | // Found the end of a `children.iter()` iterator. | |
|
139 | if let Some((key, child_node, next_iter)) = stack.pop() { | |
|
140 | // "Return" from pseudo-recursion by restoring state from the | |
|
141 | // explicit stack | |
|
142 | iter = next_iter; | |
|
143 | ||
|
144 | Some((key, child_node)) | |
|
145 | } else { | |
|
146 | // Reached the bottom of the stack, we’re done | |
|
147 | None | |
|
148 | } | |
|
149 | }) | |
|
150 | } | |
|
151 | ||
|
152 | /// Mutable iterator for the `(entry, copy source)` of each node. | |
|
153 | /// | |
|
154 | /// It would not be safe to yield mutable references to nodes themeselves | |
|
155 | /// with `-> impl Iterator<Item = &mut Node>` since child nodes are | |
|
156 | /// reachable from their ancestor nodes, potentially creating multiple | |
|
157 | /// `&mut` references to a given node. | |
|
158 | fn iter_node_data_mut<'a>( | |
|
159 | &'a mut self, | |
|
160 | ) -> impl Iterator<Item = NodeDataMut<'a>> + 'a { | |
|
161 | // Explict stack for pseudo-recursion, see `iter_nodes` above. | |
|
162 | let mut stack = Vec::new(); | |
|
163 | let mut iter = self.root.iter_mut(); | |
|
164 | std::iter::from_fn(move || { | |
|
165 | while let Some((key, child_node)) = iter.next() { | |
|
166 | // Pseudo-recursion | |
|
167 | let data = | |
|
168 | (key, &mut child_node.entry, &mut child_node.copy_source); | |
|
169 | let new_iter = child_node.children.iter_mut(); | |
|
170 | let old_iter = std::mem::replace(&mut iter, new_iter); | |
|
171 | stack.push((data, old_iter)); | |
|
172 | } | |
|
173 | // Found the end of a `children.values_mut()` iterator. | |
|
174 | if let Some((data, next_iter)) = stack.pop() { | |
|
175 | // "Return" from pseudo-recursion by restoring state from the | |
|
176 | // explicit stack | |
|
177 | iter = next_iter; | |
|
178 | ||
|
179 | Some(data) | |
|
180 | } else { | |
|
181 | // Reached the bottom of the stack, we’re done | |
|
182 | None | |
|
183 | } | |
|
184 | }) | |
|
185 | } | |
|
98 | 186 | } |
|
99 | 187 | |
|
100 | 188 | impl super::dispatch::DirstateMapMethods for DirstateMap { |
@@ -242,6 +330,7 b' impl super::dispatch::DirstateMapMethods' | |||
|
242 | 330 | _parents: DirstateParents, |
|
243 | 331 | _now: Duration, |
|
244 | 332 | ) -> Result<Vec<u8>, DirstateError> { |
|
333 | let _ = self.iter_node_data_mut(); | |
|
245 | 334 | todo!() |
|
246 | 335 | } |
|
247 | 336 | |
@@ -278,7 +367,11 b' impl super::dispatch::DirstateMapMethods' | |||
|
278 | 367 | } |
|
279 | 368 | |
|
280 | 369 | fn copy_map_iter(&self) -> CopyMapIter<'_> { |
|
281 | todo!() | |
|
370 | Box::new(self.iter_nodes().filter_map(|(path, node)| { | |
|
371 | node.copy_source | |
|
372 | .as_ref() | |
|
373 | .map(|copy_source| (path.full_path(), copy_source)) | |
|
374 | })) | |
|
282 | 375 | } |
|
283 | 376 | |
|
284 | 377 | fn copy_map_contains_key(&self, key: &HgPath) -> bool { |
@@ -318,6 +411,8 b' impl super::dispatch::DirstateMapMethods' | |||
|
318 | 411 | } |
|
319 | 412 | |
|
320 | 413 | fn iter(&self) -> StateMapIter<'_> { |
|
321 | todo!() | |
|
414 | Box::new(self.iter_nodes().filter_map(|(path, node)| { | |
|
415 | node.entry.as_ref().map(|entry| (path.full_path(), entry)) | |
|
416 | })) | |
|
322 | 417 | } |
|
323 | 418 | } |
General Comments 0
You need to be logged in to leave comments.
Login now