Rust bindings: add a TreeVisitor

[aibaars]

This pull request adds a function for convenient Tree traversal. It's implemented with a TreeCursor and provides a higher level interface than directly using a TreeCursor.

[maxbrunsfeld]

In general, I've been trying to keep these libraries pretty minimal, not providing much functionality that could be implemented on top of the core primitives. In particular, I value having a minimal number of distinct nouns/concepts in the API.

On the other hand, I think you're right that the depth-first traversal loop can be a little tricky to write. It's kind of borderline, for me, as to whether it's worth abstracting. In the past, I've thought about adding some kind of iterator-based abstraction for it. Maybe something like:

for step in tree_cursor.traverse() {
  match step {
    TraversalStep::In(node) => {
      println!("entering node {:?}", node);

      // avoid visiting certain subtrees
      if some_condition(node) {
        step.skip();
      }
    }

    TraversalStep::Out(node) => {
      println!("leaving node {:?}", node);
    }
  }
}

The iterator API seems a bit more idiomatic to me than the visitor trait, based on my limited experience with the rust ecosystem. And it's a bit more flexible in terms of mutating your environment and use break,continue,return, etc. But I might be missing some benefits to the visitor. What do you think?

[aibaars]

On the other hand, I think you're right that the depth-first traversal loop can be a little tricky to write. It's kind of borderline, for me, as to whether it's worth abstracting.

Indeed. It took me a little while to correctly implement depth-first traversal with the TreeCursor interface. That's why I thought it would be good to make a PR so others don't have to do the same thing.

The iterator API seems a bit more idiomatic to me than the visitor trait, based on my limited experience with the rust ecosystem. And it's a bit more flexible in terms of mutating your environment and use break,continue,return, etc. But I might be missing some benefits to the visitor. What do you think?

That's an interesting idea. I'll try to implement that.

[alidn]

I wasn't able to implement an iterator-based solution, but I used closures which is similarly idiomatic:

visit_node(node, |step| match step {
    Step::In(node) => {
        if some_condition {
            return ControlFlow::Skip;
        } else {
            return ControlFlow::Continue;
        }
    }
    Step::Out(node) => {
        do_something();
        // The returned value is ignored here
        ControlFlow::Continue
    }
});

If it looks good, I'll open a pull-request. What do you think?

Implementation

pub enum ControlFlow {
      Continue,
      Skip,
      Quit,
}

pub enum Step<'a> {
    In(Node<'a>),
    Out(Node<'a>),
}

pub fn visit_node<'a, F>(node: &Node<'a>, mut visitor: F)
where
    F: FnMut(Step<'a>) -> ControlFlow,
{
    let mut cursor = node.walk();
    visitor(Step::In(cursor.node()));
    let mut recurse = true;
    loop {
        if recurse && cursor.goto_first_child() {
            recurse = match visitor(Step::In(cursor.node())) {
                ControlFlow::Continue => true,
                ControlFlow::Skip => false,
                ControlFlow::Quit => return,
            };
        } else {
            visitor(Step::Out(cursor.node()));
            if cursor.goto_next_sibling() {
                recurse = match visitor(Step::In(cursor.node())) {
                    ControlFlow::Continue => true,
                    ControlFlow::Skip => false,
                    ControlFlow::Quit => return,
                };
            } else if cursor.goto_parent() {
                recurse = false;
            } else {
                break;
            }
        }
    }
}

[ObserverOfTime]

Closing since an iterator would be preferred over a visitor.