visita  

• crates.io
• github

Elegant implementation of the Visitor Pattern in Rust

Benefits

This crate aims to simplify the process of implementing the visitor pattern by removing the need to write the "routing" logic for the visitor, the node_group macro expands to the necessary boilerplate.

The visiting logic is also represented by a trait, meaning you are free to split this logic in whichever way is best for your project.

The macros will also generate a trait bound that will enforce visitors implement the necessary visiting logic for all possible variants.

High-level

A NodeFamily is a type that represents the possible values to be visited, this is most usually an enum. the NodeFamily trait exposes two members: the Data associated type is whatever additional data we want to tag with our possible variants, such as source information; and the accept function is for visiting the node with the given Visitor.

The Node trait should be implemented for all possible variants of our NodeFamily type. it has a Family associated type, which should be the NodeFamily type this node belongs to; and an accept method which is mostly there for some convenience. Sadly, enum variants in Rust aren't treated as types, so each enum variant must be a 1-tuple containing the type implementing Node.

The Visit trait represents the process of a Visitor (Self) visiting some Node, it has a single method visit which performs this operation, with the output type being defined in its supertrait Visitor

A Visitor is a type that's capable of visiting all variants of a NodeFamily. it should implement the Visitor<N> trait, where N is the node family this visitor visits. this crate also provides a convenience macro visitor, that will expand to an implementation of the trait.

Usage:

use visita::*;

pub enum Operation { Add, Sub, Mul, Div }

// Use the `node_group` macro to annotate your group of nodes
// the `data` field allows you to attach additional data to your nodes
#[node_group(data = ())]
pub enum Expr {

  NumLit(f64),

  Binary {
    op: Operation,
    lhs: Expr,
    rhs: Expr,
  }

}

// use the `visitor` macro to annotate your visitor structs
// the `output` field marks the result of the visit operation
// this macro will require that your Visitor implements Visit for every variant in the enum
#[visitor(Expr, output = f32)]
struct Interpreter;

impl Visit<NumLit> for Interpreter {
  fn visit(&mut self, node: &NumLit, _data: &Data<Self, NumLit>) -> Self::Output {
    node.0
  }
}

impl Visit<Binary> for Interpreter {
  fn visit(&mut self, node: &Binary_data: &Data<Self, Binary>) -> Self::Output {
    match node.op {
      Operation::Add => node.lhs.accept(self) + node.rhs.accept(self),
      Operation::Sub => node.lhs.accept(self) - node.rhs.accept(self),
      Operation::Mul => node.lhs.accept(self) * node.rhs.accept(self),
      Operation::Div => node.lhs.accept(self) / node.rhs.accept(self),
    }
  }
}

Explanation:

the implementation of the pattern is split between 4 traits:

// Marks a type as a family of nodes
// and is responsible for routing the visitor to the appropriate visitor methods
pub trait NodeFamily<V> : Sized where V : Visitor<Self> {
  // The additional data we want to tag with the nodes
  type Data;
  // The method responsible for the routing
  fn accept(&self, v: &mut V) -> V::Output;
}

// Marks a type as being a node belonging to a family
pub trait Node<V> : Sized where V : Visitor<Self::Family> + Visit<Self> {
  type Family : NodeFamily<V>;

  fn accept(&self, v: &mut V, data: &Data<V, Self>) -> V::Output {
    v.visit(self, data)
  }
}

// Marks a type as being a visitor to a family of nodes
pub trait Visitor<F> : Sized where F : NodeFamily<Self> {
  // The output of performing this operation
  type Output;
}

// Implements the actual visiting logic for a specific node
// This is the only trait you'll need to implement manually
pub trait Visit<N> : Visitor<N::Family> where N : Node<Self> {
  fn visit(&mut self, node: &N, data: &Data<Self, N>) -> Self::Output;
}

the node_group macro will perform the following:

• extract the enum variants into their own structs;
• create a new enum which groups said structs;
• create a new struct which holds the node variant and the additional data;
• implement NodeFamily for said struct;
• implement Node for the struct variants;

#[node_group(data = ())]
enum Expr {
  NumLit(f32),
  Binary(Expr, Operation, Expr),
}

// Becomes:

struct NumLit(f32);

impl<V> Node<V> for NumLit
where V : Visitor<Expr> + Visit<NumLit> + Visit<Binary> {
  type Family = Expr;
}

impl NumLit {
  pub fn to_node(self, data: ()) -> Expr {
    Expr {
      node: ExprNode::NumLit(self),
      data,
    }
  }
}

struct Binary(Expr, Operation, Expr);

impl<V> Node<V> for Binary
where V : Visitor<Expr> + Visit<NumLit> + Visit<Binary> {
  type Family = Expr;
}

impl Binary {
  pub fn to_node(self, data: ()) -> Expr {
    Expr {
      node: Box::new(ExprNode::NumLit(self)),
      data,
    }
  }
}

enum ExprNode {
  NumLit(NumLit),
  Binary(Binary),
}

struct Expr {
  node: Box<ExprNode>,
  data: (),
}

impl<V> NodeFamily<V> for Expr
where V : Visitor<Expr> + Visit<NumLit> + Visit<Binary> {
  type Data = ();
  fn accept(&self, v: &mut V) -> V::Output {
    match self.node.as_ref() {
      ExprNode::NumLit(node) => v.visit(node, &self.data),
      ExprNode::Binary(node) => v.visit(node, &self.data),
    }
  }
}

To construct a node you'd use: NumLit(23.0).to_node(()).

The visitor macro simply implements the Visitor trait for a type:

#[visitor(Expr, output = f32)]
struct Interpreter;

// Becomes:

struct Interpreter;

impl Visitor<Expr> for Interpreter {
  type Output = f32;
}

Because of the bounds made by the node_group macro, marking a type as a visitor will also require that it implements Visit for every possible node inside that node family.