##// END OF EJS Templates
dirstate-tree: Add tree traversal/iteration...
Simon Sapin -
r47870:caa3031c default
parent child Browse files
Show More
@@ -43,6 +43,13 b' struct Node {'
43 children: ChildNodes,
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 impl DirstateMap {
53 impl DirstateMap {
47 pub fn new() -> Self {
54 pub fn new() -> Self {
48 Self {
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 impl super::dispatch::DirstateMapMethods for DirstateMap {
188 impl super::dispatch::DirstateMapMethods for DirstateMap {
@@ -242,6 +330,7 b' impl super::dispatch::DirstateMapMethods'
242 _parents: DirstateParents,
330 _parents: DirstateParents,
243 _now: Duration,
331 _now: Duration,
244 ) -> Result<Vec<u8>, DirstateError> {
332 ) -> Result<Vec<u8>, DirstateError> {
333 let _ = self.iter_node_data_mut();
245 todo!()
334 todo!()
246 }
335 }
247
336
@@ -278,7 +367,11 b' impl super::dispatch::DirstateMapMethods'
278 }
367 }
279
368
280 fn copy_map_iter(&self) -> CopyMapIter<'_> {
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 fn copy_map_contains_key(&self, key: &HgPath) -> bool {
377 fn copy_map_contains_key(&self, key: &HgPath) -> bool {
@@ -318,6 +411,8 b' impl super::dispatch::DirstateMapMethods'
318 }
411 }
319
412
320 fn iter(&self) -> StateMapIter<'_> {
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