pub struct Expr(pub Vec<Box<ExprItem>>);

pub enum ExprItem {
    Word(String),
    Candidates(Vec<Box<Expr>>),
}

pub fn expand(expr: &Expr, idx: usize, stack: &mut Vec<String>, callback: &Fn(&mut Vec<String>))
{
    if idx == expr.0.len() {
        callback(stack);
        return;
    }
    let item: &ExprItem = &expr.0[idx];
    match *item {
        ExprItem::Word(ref val) => {
            stack.push(val.to_owned());
            expand(expr, idx + 1, stack, callback);
            stack.pop();
        }
        ExprItem::Candidates(ref candidates) => {
            if candidates.is_empty() {
                expand(expr, idx + 1, stack, callback);
            } else {
                for candidate in candidates {
                    expand(&candidate, 0, stack, &|res| {
                        expand(expr, idx + 1, res, callback);
                    });
                }
            }
        }
    }
}

fn main() {
    let expr = Expr(vec![
        Box::new(ExprItem::Word("hello".to_owned())),
        Box::new(ExprItem::Candidates(vec![
            Box::new(
                Expr(vec![Box::new(ExprItem::Word("a".to_owned()))])
            ),
            Box::new(
                Expr(vec![Box::new(ExprItem::Word("b".to_owned()))])
            ),
        ])),
        Box::new(ExprItem::Candidates(vec![
            Box::new(
                Expr(vec![Box::new(ExprItem::Word("c".to_owned()))])
            ),
            Box::new(
                Expr(vec![Box::new(ExprItem::Word("d".to_owned()))])
            ),
        ])),
        Box::new(ExprItem::Candidates(vec![])),
        Box::new(ExprItem::Word("world".to_owned())),
    ]);
    let mut stack = Vec::new();
    expand(&expr, 0, &mut stack, &|res: &mut Vec<String>| {
        println!("{}", res.join("-"));
    });
}