Zipping two visitors

[gaetanww]

Is it possible to zip two visitors? That is, walk through two structures of the same type in parallel and visit pairs of values?

[nikis05]

Unfortunately it is not currently possible, but I will implement it for you if you are ready to wait till Thursday.

[gaetanww]

Thanks, so much! My use-case is using the Visitor pattern to diff recursively two rust structures.

[lovasoa]

Maybe a thing to do would be to implement a visiting Iterator ? zip would automatically become available, as well as many other features, for "free".

[nikis05]

The way it currently works, driving is stateless, there is just a bunch of functions that get called sequentially, so there is no way to pause / suspend the process of driving a visitor. Which also makes it impossible to do anything similar to zip. For this reason I really like the iterator idea, a stateful iterator could be created from any Drive implementor and would have all of the regular iterator capabilities out of the box.

Now there are two ways to implement it.

1. Simple way - when constructed, iterator visits the entire tree and buffers references to everything. Then gives them away one at a time when iterated. This approach will require the buffering of all references, and will only work for non-mut visits.
2. Hard way - change signature of Drive so that it supports retrieving a reference to a single item "on demand". Something like this:

trait Drive {
    fn lookup(&self, cursor: Cursor) -> (&dyn Any, Option<Cursor>);

    fn drive<V: Visitor>(&self, visitor: &V) {
        // Default implementation is provided
        todo!()
    }
}

struct Cursor(usize);

impl Cursor {
    pub fn start() -> Self {
        Self(0)
    }
}

[lovasoa]

Option 2 offers more possibilities 😃

[nikis05]

True, I also prefer option 2. Then the question is, how to properly handle mutability?

For example in the following scenario:

1. user obtains a reference to a Vec through a mutable visitor;
2. down the visiting road, user obtains a cursor to an item of that vec;
3. item is then removed;
4. cursor now becomes invalid.

Should I panic in this scenario, and ditch the idea of an opaque cursor in favour of simple usize, and let user know that he needs to handle this scenario manually? Or should I add PhantomData to cursor and make it behave as though it borrows from the Drive implementor?

[lovasoa]

It's probably safer to make sure the Vec is borrowed so that it cannot be mutated while its children are being visited, no ?

[nikis05]

Edge case: last element of the struct that I'm visiting is a vec. I call lookup and obtain a mutable reference to the vec, and the cursor which points to the first element of the vec. I clear the vec. Cursor now points to nothing

[nikis05]

@gaetanww Implementing this feature properly would require a major rewrite of this library which I currently don't have the resources to do. For now I recommend you use the following pattern:

1. Create a visitor that collects references into Vec:

struct IterableVisitor(Vec<&dyn Any>);

impl Visitor for IterableVisitor {
     fn visit(&mut self, item: &dyn Any, event: Event) {
        if matches!(event, Event::Enter) {
            self.0.push(item);
        }
     }
}

2. Create an iterator from that visitor:

impl IterableVisitor {
    fn iter(&self) -> impl Iterator<Item = &dyn Any> {
        self.0.iter()
    }
}

3. Drive the two visitors, then create iterators from them and zip them

4. For each item (which would be a tuple of values) in resulting iterator, call visitor.visit(item, Event::Enter). You can then visit pairs of values.

[gaetanww]

Thank you very much for looking into it :) This approach seems reasonable for now.

[nikis05]

I will keep the issue open to come back to it when I can

[lovasoa]

I played a little bit with the idea, but haven't really solved the problem yet:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=432e19d6a40fe54a9632f77c44b06622

[Nadrieril]

@lovasoa nice! I took your idea and I ran with it: https://github.com/Nadrieril/type-walker. It turns out this is a special case of a lending iterator, so I built that crate on top of lending_iterator.

Incidentally, that design also solves #5 since we can stop calling next_field() whenever we want.

One problem is that since visitors for the fields capture a &mut to the fields, we can't keep a &mut to the parent struct around, which we need for the Event::Exit. I had to use unsafe to make that work. Once generators support lending iterators, they can be used instead since they do exactly the kind of unsafe I had to do. This doesn't affect users because the unsafe is hidden behind the safe walk_inner interface.