introduce a Visit trait to go with Fold

[nikomatsakis]

Right now we have a Fold trait that is used to transform types and other bits of IR. But sometimes we don't need to recreate the IR, we instead want to compute a value (e.g., count all the types etc). You can model this as a folder with mutable state, but it'd be more efficient to have a "visitor" trait.

Some examples where this would be useful:

• the truncator is right now only used to detect when terms get too big
• the UCollector
• the needs_shift method
• some upcoming work as well

[nikomatsakis]

One question is how general to make the trait. The trait in rustc hardcodes returning a bool. I was imagining we might want something more general. I actually implemented this once but I can't find the branch. It looked something like:

trait Visitor {
    type Result: VisitorResult;
    fn visit_ty(&mut self, ty; &Ty) -> Self::Result; 
    fn visit_lifetime(&mut self, ty; &Lifetime) -> Self::Result; 
}

To actually visit things, you used the visit_with method from the Visit trait (which was derivable):

trait Visit {
  fn visit_with<R>(&self, visitor: &mut dyn Visitor<Result = R>) -> R;
}

trait VisitResult {
  fn new() -> Self;
  fn and_then(self, op: impl FnOnce() -> Self) -> Self;
}

The derive for a struct like struct Foo { a, b } might look like:

impl Visit for Foo {
  fn visit_with<R>(&self, visitor: &mut dyn Visitor<Result = R>) -> R {
    let Foo { a, b } = self;
    R::new()
      .and_then(|| a.visit_with(visitor))
      .and_then(|| b.visit_with(visitor))
  }
}

The VisitResult trait was designed to have various sorts of visitors, some of which "stop early" and abort the visit. Example:

struct FindAny(bool);

impl VisitResult for FindAny{
  fn new() -> FindAny {
    FindAny(false)
  }

  fn and_then(self, op: impl FnOnce() -> FindAny) -> FindAny {
    if self.0 { self } else { op() }
  }
}

You could also implement a counter etc:

struct Counter(usize);

impl VisitResult for Counter{
  fn new() -> Counter {
    Counter(0)
  }

  fn and_then(self, op: impl FnOnce() -> FindAny) -> Counter {
    Counter(self.0 + op().0)
  }
}

[nikomatsakis]

The steps to implement this are probably:

• add the trait
• you could start out by writing a wrapper that abuses Fold, but that might not be worth it
• write the derive in the chalk-derive crate
• start to replace uses of Fold

[jackh726]

This seems like a fairly easy issue to try to implement, so I'll mark it as such.

[SuhasHebbar]

Hello,
I am new to rust and haven't worked on writing macros yet.
I have started reading the chalk book and the blog posts linked in the README.

From what I could understand the work here involves

• Adding the Visitor, VisitResult traits similar to what has been described above. These essentially seem to be a more general implementation of the Fold trait.
• Write the derive for Visitor based on derive_fold which should essentially behave the same as derive_fold except using Visitor instead (and then remove derive_fold?).
• Start replacing manual impls of Fold with Visitor.

Am I misunderstanding anything here?

[shepmaster]

I don't know if any of this is relevant to Chalk, but as a bit of "here's another example of a visitor", when I created a visitor for fuzzy-pickles, it had a few components:

• Visit

A trait that each node in the AST implemented. This was the trait that has a corresponding derive macro.

• Visitor
• VisitorMut

Each unique pass implements one of these traits. They have a huge number of methods: two for each corresponding AST node type, one on entry to the node, one on exit. Every method has a default implementation so that a specific implementation only needs to hook into the AST nodes it is interested in.

The primary difference in the traits is in the signatures:

trait Visit {
    fn visit_array(&mut self, &'ast Array) -> Control
}

trait VisitMut {
    fn visit_array(&mut self, &mut Array) -> Control
}

[jackh726]

@SuhasHebbar sound about right. Just want to clarify that not all Fold impls will be Visitors. If you want to take this on, but want some guidance or discussion, free free to join us on the wg-traits stream on zulip.

@shepmaster another (more relevant) example would the Visitor in rustc: https://github.com/rust-lang/rust/blob/master/src/librustc/ty/fold.rs#L198

[basil-cow]

I would like to pick this one up, but I am not really sure about the design: what are the benefits of using VisitResult over mutable state? Benefits I see is a) separating out the logic of whether to stop the visit based on the result to avoid repeating it after each visit b) having an explicit bottom-up structure for the answers. a) is applicable to mutable state too, so I am guessing you are interested in b), what are the reasons for this? Also that design creates an ambiguity in whether to place the logic into mutable state or VisitResult, because, for example, implementation of UCollector in terms of VisitResult is hard to make efficient.

[nikomatsakis]

So @jackh726 created a Zulip thread for this discussion. (thanks, I find it hard to keep up with gh notifications for this sort of thing...)