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 :smiley:

[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 https://github.com/nikis05/derive-visitor/issues/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.

[Nadrieril]

Zipping two lending iterators is easy (implementation). Zipping two TypeWalkers is not quite possible, because we can't zip two &mut dyn Any into a &mut dyn Any that represents the pair. Note also that if we're walking over two enums of the same type, if they have different variants then the visited types won't match anymore. We can still provide a decent API for that though.

EDIT: I added the following API:

/// Zips a number of identical walkers. Assuming they output the same types and events in the
/// same order, this can be used to iterate over multiple values in lockstep. The output is not
/// a `TypeWalker` because the types don't match, however it has appropriate convenience
/// methods to consume it.
pub fn zip_walkers<I: TypeWalker, const N: usize>(walkers: [I; N]) -> ZipWalkers<I, N> { .. }
pub fn zip_walkables<T: Walkable, const N: usize>(walkables: [&mut T; N]) -> ZipWalkers<T::Walker<'_>, N> { .. }

impl<I: TypeWalker, const N: usize> ZipWalkers<I, N> {
    /// Returns the next array of values of type `T`.
    pub fn next_t<T: 'static>(&mut self) -> Option<([&mut T; N], Event)> { .. }
}

// Can be used like:
let mut p = Point { x: 10, y: 20 };
let mut q = Point { x: 100, y: 200 };
let mut zip = zip_walkables([&mut p, &mut q]);

let ([p_x, q_x], _) = zip.next_t::<u8>().unwrap();
let ([p_y, q_y], _) = zip.next_t::<u8>().unwrap();
...