Fallible visitors / early exit?

[nikis05]

I can see some use cases where visitors might want to quit walking the hierarchy early, e.g. a validator visitor that exits on the first error, or a counter visitor that exits when a certain count is reached.

A few questions need to be answered:

1. Does anyone need this?
2. Should Visitor / Drive be subtraits of FallibleVisitor / FallibleDrive that panic on error, or should these be completely separate traits?
3. Are Result type, "fallible", etc applicable terminology for this? Early exit doesn't always mean error.

[badicsalex]

I actually do visitors that have to report errors. Right now I use it as:

    fn get_all_stuff(&self) -> Result<Vec<ProcessedStuff>> {
        let mut result: Vec<Result<ProcessedStuff>> = Vec::new();
        self.drive(&mut visitor_enter_fn(|stuff: &Stuff| ... ));
        // Transpose Vec<Result> to Result<Vec>
        result.into_iter().collect()
    }

Some convenience and performance gains could be had by not doing the final transpose step. Then again, this is a very niche use-case and I don't need neither convenience nor performance here.

[badicsalex]

The pattern I see with tree visitors is that you can return 3 different outcomes from bot the enter and exit function: Continue, Skip, StopCompletely.
Skip means "skip the interior" when returned from enter, and "skip siblings" when returned from exit.
Stop completely is usually implemented with an exception in exception-using languages.

I'd call it ShortCircuitingVisitor, and would actually blanket impl<T> ShortCircuitingVisitor<T> for Visitor<T>, returning Continue every time.
Then you would only need a single type of Drive accepting a ShortCircuitingVisitor, which returns if it was stopped prematurely or not.

[nikis05]

Good idea. I'll implement it if I receive a one more request for this, or if I'll find that I need it myself

[nikis05]

A few issues to consider:

1. Should we change existing Visitor trait's return type or introduce a new trait, say ShortCircuitingVisitor, and blanket implement that new trait for regular Visitor. The downside of the first option is that all visitor implementations, even the ones that don't need early exit, would need to return a Continue. The downside of the second option is that it might be confusing - e.g. instead of a method that accepts a Visitor there would be a method that accepts a ShortCircuitingVisitor, one would then need to look through the docs and see what a ShortCircuitingVisitor is, and notice that it has a blanket implementation.
2. What would the name of the new trait be? ShortCircuitingVisitor, EarlyExitVisitor, ControllableVisitor, ControlFlowVisitor are some of the ideas I have, but they all still seem confusing to me.

For these reasons, I would rather modify the existing trait. However, I would redesign the #[derive(Visitor)] macro like so:

#[derive(Visitor)]
#[visitor(Folder(enter), File(enter, flow)]
struct SomeVisitor;

impl SomeVisitor {
    // this method must return (), which is interpreted as `Flow::Continue`
    fn enter_folder(&mut self, item: &Folder) {
        // ...
    }

    // this method must return `Flow`
    fn enter_file(&mut self, item: &File) -> Flow {
        // ...
        if self.some_condition {
            Flow::Continue
        } else {
            Flow::Exit
        }
    }
}

This would enable early exit / skipping in implementations while defaulting to regular behavior.

3. If we change the existing trait, how should we treat fn / closure visitors? Should they also return () and always continue?

4. I think @badicsalex's proposal for Flow::Skip behavior to depend on whether it is returned from an enter or an exit method might be counterintuitive / obscure. On the other hand, it is impossible to "skip inner" in the exit method, because the inner items would have already been visited. How should we deal with it?

[badicsalex]

For 4, you could always just introduce two enums (EnterFlow and ExitFlow I guess?), and call the Skip version "SkipChildren", and SkipSiblings.

I like the macro extension.

I think that the closure visitor is mainly a convenience function that should remain super simple to use.

[lewiszlw]

I vote for this feature. Maybe we can refer to datafusion-sqlparser's design.
https://github.com/apache/datafusion-sqlparser-rs/blob/b1b379e57086ad7fcfa67136c0c64b14d4efab9d/src/ast/visitor.rs#L291-L294

[lewiszlw]

If you @nikis05 agree, I can work on this.