Shared via Rust Playground

playground.rs

// I'm cheating slightly by using features that aren't entirely stable yet.
// The reason is simple: the box matching code below becomes somewhat messier
// without `box_patterns`, and `box x` becomes `Box::new(x)` without
// `box_syntax`.
// This was tested on `play.rust-lang.org`'s nightly channel on 2015-08-03.
#![feature(box_patterns)]
#![feature(box_syntax)]

// Moo!
use std::borrow::Cow;

// Promote the `Expr` variants to module scope.  Otherwise, we'd have to say
// `Expr::Add` instead of `Add`.
use Expr::*;

/// A sum type for the expression.
/// An expression is either a var (which is a string), a constant
/// (which is an integer), an addition (made of two expressions)
/// or a multiplication (also made of two expressions).
enum Expr {
    Var(String),
    Const(i32),
    Add(Box<Expr>, Box<Expr>), // Rust needs an indirection here to break the
    Mul(Box<Expr>, Box<Expr>), // cycle.  Could also have used pointers.
}

impl Expr {
    /// Simplify a single component of the expression. This function
    /// takes the expression and uses pattern matching to select the
    /// right approach based on type and value. For example, if we
    /// add a constant 0 to some x (which can be expression), then
    /// we return x.
    fn simplify1(self) -> Expr {
        match self {
            // `box` in a pattern *deconstructs* a Box,
            // `box` in an expression *constructs* a Box.
            Add(box Const(0), box x)
            | Add(box x, box Const(0))
            | Mul(box Const(1), box x)
            | Mul(box x, box Const(1)) => x,

            Mul(box Const(0), _) // _ means "don't care"
            | Mul(_, box Const(0)) => Const(0),

            Add(box Const(a), box Const(b)) => Const(a + b),
            Mul(box Const(a), box Const(b)) => Const(a * b),
            e => e
        }
    }

    /// Recursive function to simplify an entire expression.
    #[cfg(needless_heap_usage)] // Use conditional compilation.
    fn simplify(self) -> Expr {
        match self {
            Add(box x, box y) => Add(box x.simplify(), box y.simplify()),
            Mul(box x, box y) => Mul(box x.simplify(), box y.simplify()),
            e => e
        }.simplify1()
    }

    /// Recursive function to simplify an entire expression.
    /// Avoid unnecessary heap activity at the cost of being more verbose.
    #[cfg(not(needless_heap_usage))]
    fn simplify(mut self) -> Expr {
        // We want to avoid unnecessary heap activity; to do that, we'll just
        // operate on the contents of the boxes by taking mutable borrows of
        // the interior, rather than deconstructing the box entirely.
        //
        // This is a little tricky because `simplify` expects to be able to
        // take ownership of the value, and this means we need to *move* the
        // contents of the box out... but this *destroys* the box (a box can't
        // have nothing in it).  So what do we do?  We use `replace`!
        //
        // `std::mem::replace` is a swap where one of the values is just
        // provided by-value as an argument instead of being an actual variable.
        // We use a `Const(0)` (which is cheap to construct) to fill the box
        // and keep it from being destroyed, then immediately overwrite it.
        //
        // This is mostly just to show how high-level functional constructs
        // can be mixed with low-level concerns.
        use std::mem::replace;
        match self {
            Add(box ref mut x, box ref mut y) => {
                *x = replace(x, Const(0)).simplify();
                *y = replace(y, Const(0)).simplify();
            },
            Mul(box ref mut x, box ref mut y) => {
                *x = replace(x, Const(0)).simplify();
                *y = replace(y, Const(0)).simplify();
            },
            _ => ()
        }
        self.simplify1()
    }

    /// Return the value string if the expression can be reduced to a constant.
    fn expr_str(&self) -> Cow<'static, str> {
        // Moo!  In this case, `Cow` means `Clone on Write`, but we're using it
        // for a different purpose: this lets us have a string value which is
        // *either* an owned, heap-allocated String value (as in the first
        // branch), *or* a static string constant (as in the second branch).
        // This means that we don't do redundant allocations for the second
        // case while still allowing dynamic strings for the first.
        //
        // Also, `if let` is basically just another way of writing a match
        // which has one pattern arm and one "everything else" arm.
        //
        // Also, also; normally you wouldn't write this *at all*; you'd
        // implement the `std::fmt::Display` trait instead, then just directly
        // display the `Expr`.  I really just did this because `Cow` is amusing.
        if let Const(ref x) = *self {
            x.to_string().into()
        } else {
            "The expression could not be simplified to a constant.".into()
        }
    }
}

fn main() {
    // Explicit boxing makes this a bit more verbose.  On the bright side, it's
    // pretty clear when, and how often you're allocating.
    let expr = Add(
        box Mul(
            box Add(box Const(1), box Mul(box Const(0), box Var("x".into()))),
            box Const(3)
        ),
        box Const(12)
    );
    println!("{}", expr.simplify().expr_str());
}