( )⚙ D10370 dirstate-tree: Add tree traversal/iteration

This is an archive of the discontinued Mercurial Phabricator instance.

Differential D10370

dirstate-tree: Add tree traversal/iteration
ClosedPublic

Authored by SimonSapin on Apr 12 2021, 8:23 AM.

Details

Reviewers
Alphare
Group Reviewers
hg-reviewers
Commits
rHGcaa3031c9ed5: dirstate-tree: Add tree traversal/iteration
rHGfb96635ba733: dirstate-tree: Add tree traversal/iteration
Summary

Like Python’s, Rust’s iterators are "external" in that they are driven
by a caller who calls a next method. This is as opposed to "internal"
iterators who drive themselves and call a callback for each item.

Writing an internal iterator traversing a tree is easy with recursion,
but internal iterators cannot rely on the call stack in that way,
they must save in an explicit object all state that they need to be
preserved across two next calls.

This algorithm uses a Vec as a stack that contains what would be
local variables on the call stack if we could use recursion.

Diff Detail

Repository
rHG Mercurial
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

SimonSapin created this revision.Apr 12 2021, 8:23 AM
baymax updated this revision to Diff 27053.Apr 19 2021, 11:02 AM

✅ refresh by Heptapod after a successful CI run (🐙 💚)

Alphare accepted this revision.Apr 19 2021, 12:00 PM
SimonSapin added a commit: rHGfb96635ba733: dirstate-tree: Add tree traversal/iteration.May 6 2021, 12:50 PM
This revision was not accepted when it landed; it landed in state Needs Review.
Closed by commit rHGfb96635ba733: dirstate-tree: Add tree traversal/iteration (authored by SimonSapin). · Explain Why
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 27644

rust/hg-core/src/dirstate_tree/dirstate_map.rs

#[derive(Default)] #[derive(Default)]
struct Node { struct Node {
entry: Option<DirstateEntry>, entry: Option<DirstateEntry>,
copy_source: Option<HgPathBuf>, copy_source: Option<HgPathBuf>,
children: ChildNodes, children: ChildNodes,
} }
/// `(full_path, entry, copy_source)`
type NodeDataMut<'a> = (
&'a WithBasename<HgPathBuf>,
&'a mut Option<DirstateEntry>,
&'a mut Option<HgPathBuf>,
);
impl DirstateMap { impl DirstateMap {
pub fn new() -> Self { pub fn new() -> Self {
Self { Self {
parents: None, parents: None,
dirty_parents: false, dirty_parents: false,
root: ChildNodes::new(), root: ChildNodes::new(),
} }
} }
if let Some(next) = inclusive_ancestor_paths.next() { if let Some(next) = inclusive_ancestor_paths.next() {
ancestor_path = next; ancestor_path = next;
child_nodes = &mut child_node.children; child_nodes = &mut child_node.children;
} else { } else {
return child_node; return child_node;
} }
} }
} }
fn iter_nodes<'a>(
&'a self,
) -> impl Iterator<Item = (&'a WithBasename<HgPathBuf>, &'a Node)> + 'a
{
// Depth first tree traversal.
//
// If we could afford internal iteration and recursion,
// this would look like:
//
// ```
// fn traverse_children(
// children: &ChildNodes,
// each: &mut impl FnMut(&Node),
// ) {
// for child in children.values() {
// traverse_children(&child.children, each);
// each(child);
// }
// }
// ```
//
// However we want an external iterator and therefore can’t use the
// call stack. Use an explicit stack instead:
let mut stack = Vec::new();
let mut iter = self.root.iter();
std::iter::from_fn(move || {
while let Some((key, child_node)) = iter.next() {
// Pseudo-recursion
let new_iter = child_node.children.iter();
let old_iter = std::mem::replace(&mut iter, new_iter);
stack.push((key, child_node, old_iter));
}
// Found the end of a `children.iter()` iterator.
if let Some((key, child_node, next_iter)) = stack.pop() {
// "Return" from pseudo-recursion by restoring state from the
// explicit stack
iter = next_iter;
Some((key, child_node))
} else {
// Reached the bottom of the stack, we’re done
None
}
})
}
/// Mutable iterator for the `(entry, copy source)` of each node.
///
/// It would not be safe to yield mutable references to nodes themeselves
/// with `-> impl Iterator<Item = &mut Node>` since child nodes are
/// reachable from their ancestor nodes, potentially creating multiple
/// `&mut` references to a given node.
fn iter_node_data_mut<'a>(
&'a mut self,
) -> impl Iterator<Item = NodeDataMut<'a>> + 'a {
// Explict stack for pseudo-recursion, see `iter_nodes` above.
let mut stack = Vec::new();
let mut iter = self.root.iter_mut();
std::iter::from_fn(move || {
while let Some((key, child_node)) = iter.next() {
// Pseudo-recursion
let data =
(key, &mut child_node.entry, &mut child_node.copy_source);
let new_iter = child_node.children.iter_mut();
let old_iter = std::mem::replace(&mut iter, new_iter);
stack.push((data, old_iter));
}
// Found the end of a `children.values_mut()` iterator.
if let Some((data, next_iter)) = stack.pop() {
// "Return" from pseudo-recursion by restoring state from the
// explicit stack
iter = next_iter;
Some(data)
} else {
// Reached the bottom of the stack, we’re done
None
}
})
}
} }
impl super::dispatch::DirstateMapMethods for DirstateMap { impl super::dispatch::DirstateMapMethods for DirstateMap {
fn clear(&mut self) { fn clear(&mut self) {
self.set_parents(&DirstateParents { self.set_parents(&DirstateParents {
p1: NULL_NODE, p1: NULL_NODE,
p2: NULL_NODE, p2: NULL_NODE,
}); });
Ok(Some(parents)) Ok(Some(parents))
} }
fn pack( fn pack(
&mut self, &mut self,
_parents: DirstateParents, _parents: DirstateParents,
_now: Duration, _now: Duration,
) -> Result<Vec<u8>, DirstateError> { ) -> Result<Vec<u8>, DirstateError> {
let _ = self.iter_node_data_mut();
todo!() todo!()
} }
fn build_file_fold_map(&mut self) -> &FastHashMap<HgPathBuf, HgPathBuf> { fn build_file_fold_map(&mut self) -> &FastHashMap<HgPathBuf, HgPathBuf> {
todo!() todo!()
} }
fn set_all_dirs(&mut self) -> Result<(), DirstateMapError> { fn set_all_dirs(&mut self) -> Result<(), DirstateMapError> {
todo!() todo!()
} }
fn copy_map_len(&self) -> usize { fn copy_map_len(&self) -> usize {
todo!() todo!()
} }
fn copy_map_iter(&self) -> CopyMapIter<'_> { fn copy_map_iter(&self) -> CopyMapIter<'_> {
todo!() Box::new(self.iter_nodes().filter_map(|(path, node)| {
node.copy_source
.as_ref()
.map(|copy_source| (path.full_path(), copy_source))
}))
} }
fn copy_map_contains_key(&self, key: &HgPath) -> bool { fn copy_map_contains_key(&self, key: &HgPath) -> bool {
if let Some(node) = self.get_node(key) { if let Some(node) = self.get_node(key) {
node.copy_source.is_some() node.copy_source.is_some()
} else { } else {
false false
} }
self.get(key).is_some() self.get(key).is_some()
} }
fn get(&self, key: &HgPath) -> Option<&DirstateEntry> { fn get(&self, key: &HgPath) -> Option<&DirstateEntry> {
self.get_node(key)?.entry.as_ref() self.get_node(key)?.entry.as_ref()
} }
fn iter(&self) -> StateMapIter<'_> { fn iter(&self) -> StateMapIter<'_> {
todo!() Box::new(self.iter_nodes().filter_map(|(path, node)| {
node.entry.as_ref().map(|entry| (path.full_path(), entry))
}))
} }
} }