Implement the visitor pattern

help
#1

Hello,
I'm quite new to rust and I'd like to implement the visitor pattern for a little side-project.
I'm stuck attempting to hide the mutability of the visitor, so I guess I'm missing something obvious (sorry for that in advance !)

here's a minimal example :

trait Visitor {
  fn visit(&self);
}

fn walk(v: &dyn Visitor){
  v.visit();
}

struct DummyVisitor;
impl Visitor for DummyVisitor {
  fn visit(&self){
    println!("dummy")
  }
}

struct AccumVisitor{
  i: u8,
}

impl AccumVisitor {
  fn visit(&mut self){
    self.i += 1;
  }
}

// err : expected fn pointer `fn(&AccumVisitor)`found fn pointer `fn(&mut AccumVisitor)`
//
// impl Visitor for AccumVisitor {
//   fn visit(&mut self){
//     self.i += 1;
//   }
// }


// err: `self` is a `&` reference, so the data it refers to cannot be written
//
//impl Visitor for &mut AccumVisitor {
//  fn visit(&self){
//    self.i += 1;
//  }
//}


fn main() {
  let vd = DummyVisitor;
  walk(&vd);

  let va = &mut AccumVisitor{i:0};
  // walk(&va)

  va.visit();
}

Best,

#2

The visitor is usually going to want to modify itself during iteration, so it makes sense to use a mutable reference to it. You’re also going to need to pass the current node to the visitor somehow, and you likely want that to be an immutable reference (assuming the purpose of this visitor is purely for inspection). I’d probably define a pair of traits for this: one that describes the nodes and another for the visitors:

trait Visitable {
    /// Override this for collections that contain several nodes
    fn walk(&self, visitor: &mut impl Visitor) {
        visitor.visit(self);
    }

    /* Other access methods */
}

trait Visitor {
    fn visit(&mut self, node:&impl Visitable);
}
1 Like
#3

Thanks @2e71828 actually, I'd like not to assume if the visitor mutates itself or not (neither use the mut receiver everywhere to get the guarantee of no mutation if it's in the type signature).
And yes, I removed all implementation details about nodes and other stuff.

Also, I found an article called "Abstracting over mutability in Rust".
It looks like the kind of things I try to do (but I'm not 100% sure)... I just have to figure out how it works. :slight_smile:

Any advises to solve this in the most idiomatic possible way ?
Thanks again.

#4

For inspiration, see what the ::syn crate does: it uses two Visitor traits:

  • Visit, with &mut Self, &'ast Node (note the fixed lifetime on the Node, it allows Self to store references to the inspected stuff (no need to .clone() stuff);

  • VisitMut, with &mut Self, &'_ mut Node (gets to mutate the inspected stuff, but it thus cannot keep references to it).

As you can see, both traits, even the Visit one, use &mut Self for the receiver, for the reasons @2e71828 mentioned.

4 Likes
#5

Honestly, most visitor patterns I've seen was just a poor man's ADT. In Rust we have real ADT as a combination of enum and struct so you may not need the pattern at all.

You can find some libraries of Rust provides the visitor API, because it want to squeeze the last performance from the machine so it cannot even aware of the single tag byte(serde) or the structure is so complex and in most case you only want to handle small parts of it(syn). If you want a full traversal and can waste dozen nanoseconds per operations, use enum with match.

1 Like
#6

Just to add a bit of distance w.r.t. the design you are attempting to do:

  1. & stands for shared reference, used for concurrent accesses; whereas &mut stands for exclusive reference, thus used for sequential accesses. The fact that &mut offers mutability for free is a neat side-effect of the exclusivity, in the same fashion that &-shared/concurrent access is usually tied to immutability, but not always.

  2. So, a visit_thing (&self, …) API is actually expressing that the mechanism performing the visit is doing so in a concurrent fashion, which is … weird unless multi-threading is involved, in which case parallel accesses make sense (but then you'd need a Sync super bound on the trait).

  3. If, for some reason, you had to deal with a &self API but you wanted mutation, because, for some reason, you know there won't be concurrent accesses, you can "assert so" using a runtime-checked mechanism against concurrent accesses:

    • For parallel accesses, you can wrap some fields of Self in a RwLock; or, should they be small and simple enough (such as integers), you can wrap them in an AtomicCell (which does not deadlock/panic! should concurrent single-threaded access (re-entrancy) occur).

    • For the single-threaded case, you can soothe a bit the stuff and use the slightly faster RefCell and Cell respective equivalents (the latter does not panic! should concurrent access occur).

    Example:

    trait Visitor {
    fn visit (self: &'_ Self)
    ;
}

fn walk (v: &'_ dyn Visitor)
{
    v.visit();
}

struct DummyVisitor;
impl Visitor for DummyVisitor {
    fn visit (self: &'_ Self)
    {
        println!("dummy")
    }
}

use ::core::cell::Cell as Mut;
struct AccumVisitor {
    i: Mut<u8>,
}

// No error.
impl Visitor for AccumVisitor {
    fn visit (self: &'_ Self)
    {
        self.i.set(self.i.get() + 1);
    }
}

fn main ()
{
    let vd = DummyVisitor;
    walk(&vd);

    let va = AccumVisitor { i: Mut::new(0) };
    walk(&va)

    va.visit();
}
2 Likes
#7

This makes it hard to give you good advice: Rust design patterns don’t map particularly well to C++ / Java ones, so it’s easier to reason about the concrete problem you’re trying to solve instead of how to implement a foreign-language pattern.

As @Hyeonu mentioned, just because a Visitor is the best solution in some other language doesn’t mean it’s also the best choice in Rust. Or even that all those problems have the same solution in Rust: There are often multiple Rust “equivalents” with varying strengths and weaknesses compared to the foreign pattern.

1 Like
#8

Thanks a lot @Yandros your answer is really great !

I found you wrote 3 articles about mutability in rust, I'll read them, looks quite complete.

Thanks !

1 Like
#9

:smile: There are also two other articles that are more succinct and thus ought to be easier to digest:

1 Like
#10

great ! reading your articles was actually quite enlightening !

For those interested, here's another, quite simple, fix :

trait Visitor {
  fn visit(&self);
}

fn walk(v: &dyn Visitor){
  v.visit();
}

struct DummyVisitor;
impl Visitor for DummyVisitor {
  fn visit(&self){
    println!("dummy")
  }
}


use std::sync::atomic::{AtomicU32, Ordering::Relaxed};
struct AccumVisitor{
  i:  AtomicU32,
}

impl Visitor for AccumVisitor {
  fn visit(&self){
    self.i.fetch_add(1, Relaxed); // EDIT after @2e71828 comment : atomic version of the 3 lines below

    // self.i.store(
    //  self.i.load(Relaxed) + 1, Relaxed
    //);
  }
}

fn main() {
  let vd = DummyVisitor;
  walk(&vd);

  let va = AccumVisitor{i: AtomicU32::new(0)};
  walk(&va);
  walk(&va);

  println!("{:?}", &va.i)
}
#11

This is better written as:

self.i.fetch_add(1, Relaxed);

Your current version has a potential race condition where another thread modifies the count between the load and store operations.

2 Likes
#12

thanks a lot, quite a classic, indeed !
I updated my code above.