Crate uniplate

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 std::collections::VecDeque;
use uniplate::Biplate;
fn var_names(expr: &Expr) -> Vec<String>{
    let names: VecDeque<String> = expr.universe_bi();
    names.into()
}

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 (transform, descend) and fold(cata.

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::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::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 nested 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::{Uniplate,Biplate};
use std::collections::VecDeque;
#[derive(Clone,PartialEq,Eq,Debug,Uniplate)]
#[biplate(to=String)]
#[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>{
    let names: VecDeque<String> = stmt.universe_bi();
    names.into()
}

§Bibliography

The techniques implemented in this crate originate from the following:

Modules§

impl_helpers
Helper functions for manually implementing Uniplate and Biplate instances.
spez
Auto-deref specialization helpers for the derive macro.
tagged_zipper
A Tagged Zipper is a wrapper around a Zipper that allows for attaching arbitrary data to each node.
zipper
Cursors into Uniplate types.

Macros§

derive_iter
Generates Biplate and Uniplate instances for a collection using its Iterator implementation.
derive_unplateable
Generates Biplate and Uniplate instances for an unplateable type.

Enums§

Tree
Tree stores the children of type T of a value, preserving its structure.

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.

Derive Macros§

Uniplate
The Uniplate derive macro.