Crate uniplate

Source
Expand description

Uniplate helps you write simple, boilerplate-free operations on tree shaped data types.

  • A port of Haskell’s Uniplate library in Rust.

§Getting Started

Adapted from (Mitchell and Runciman 2007)

Consider the abstract syntax tree for a simple calculator language:

enum Expr {
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Div(Box<Expr>, Box<Expr>),
    Val(i32),
    Var(String),
    Neg(Box<Expr>),
}

Say we want to list all the used variable names inside a given expression:

fn var_names(expr: &Expr) -> Vec<String>{
    match expr {
        Add(a,b) => {
            [var_names(a),var_names(b)].concat()
        },
        Sub(a,b) => {
            [var_names(a),var_names(b)].concat()
        },
        Mul(a,b) => {
            [var_names(a),var_names(b)].concat()
        },
        Div(a,b) => {
            [var_names(a),var_names(b)].concat()
        },
        Val(a) => {
            Vec::new()
        },
        Var(a) => {
            vec![a.clone()]
        },
        Neg(a) =>{
            var_names(a)
        }
    }
}

Functions like these are annoying to write: the first 4 constructors are basically identical, adding a new expression type requires a new line to be added to all match statement, and this code cannot be shared with similar functions (e.g. one that change all the variable names).

With Uniplate, this boilerplate can be eliminated:

use uniplate::Biplate;
fn var_names(expr: &Expr) -> Vec<String>{
    <Expr as Biplate<String>>::universe_bi(expr).into_iter().collect()
}

The functionality of Uniplate comes from two main traits: Uniplate and Biplate<T>.

  • The Uniplate of Expr operates over all nested Exprs.
  • The Biplate<T> of Expr operates over all nested values of type T in the expression tree.

These traits provide traversal operations (e.g. children) as well as functional programming constructs such as map and fold. See the trait documentation for the full list of operations provided.

The easiest way to use Uniplate is with the derive macro.

§Derive Macro

To derive Uniplate instances, use the #[uniplate] attribute:

use uniplate::derive::Uniplate;
#[derive(Clone,PartialEq,Eq,Debug,Uniplate)]
#[uniplate()]
enum Expr {
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Div(Box<Expr>, Box<Expr>),
    Val(i32),
    Var(String),
    Neg(Box<Expr>),
}

To derive Biplate instances, use the #[biplate] attribute:

use uniplate::derive::Uniplate;
#[derive(Clone,PartialEq,Eq,Debug,Uniplate)]
#[biplate(to=String)]
#[biplate(to=i32)]
enum Expr {
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Div(Box<Expr>, Box<Expr>),
    Val(i32),
    Var(String),
    Neg(Box<Expr>),
}

§Multi-type traversals

Uniplate also supports trees with multiple recursive types. Lets extend our calculator language to include statements as well as expressions:

enum Expr {
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Div(Box<Expr>, Box<Expr>),
    Val(i32),
    Var(String),
    Neg(Box<Expr>),
}

enum Stmt {
    Assign(String, Expr),
    Sequence(Vec<Stmt>),
    If(Expr, Box<Stmt>, Box<Stmt>),
    While(Expr, Box<Stmt>),
}

When looking for variable names in a given statement, we want to identify not only the variable names directly used inside the statement, but also any variable names used by child expressions:

use uniplate::derive::Uniplate;
use uniplate::{Uniplate,Biplate};
#[derive(Clone,PartialEq,Eq,Debug,Uniplate)]
// look for strings inside expressions as well as statements 
#[biplate(to=String,walk_into=[Expr])]
#[biplate(to=Expr)]
#[uniplate()]
enum Stmt {
    Assign(String, Expr),
    Sequence(Vec<Stmt>),
    If(Expr, Box<Stmt>, Box<Stmt>),
    While(Expr, Box<Stmt>),
}

#[derive(Clone,PartialEq,Eq,Debug,Uniplate)]
#[biplate(to=String)]
#[uniplate()]
enum Expr {
    Add(Box<Expr>, Box<Expr>),
    Sub(Box<Expr>, Box<Expr>),
    Mul(Box<Expr>, Box<Expr>),
    Div(Box<Expr>, Box<Expr>),
    Val(i32),
    Var(String),
    Neg(Box<Expr>),
}

fn vars_names(stmt: &Stmt) -> Vec<String>{
    <Stmt as Biplate<String>>::universe_bi(stmt).into_iter().collect()
}

The types given to the walk_into argument are recursed through by uniplate. Both #[uniplate] and #[biplate] support the walk_into parameter.

§Bibliography

The techniques implemented in this crate originate from the following:

Modules§

  • derive
    The derive macro.
  • impls
    Implementations of Uniplate and Biplate for common types.

Macros§

  • derive_iter
    Generates a Biplate and Uniplate instance for an iterable type.
  • derive_unplateable
    Generates a Biplate and Uniplate instance for an unplateable type.

Traits§

  • Biplate
    Biplate<U> for type T operates over all values of type U within T.
  • Uniplate
    Uniplate for type T operates over all values of type T within T.