use rand::Rng;
use std::fs::read_to_string;

mod ast;
use ast::*;

mod parser;
use parser::*;

struct Environment {
    bindings: std::collections::HashMap<String, Value>,
}

impl Environment {
    fn new() -> Self {
        Environment {
            bindings: std::collections::HashMap::new(),
        }
    }

    fn bind(&mut self, var: &str, value: &Value) {
        self.bindings.insert(var.to_string(), value.clone());
    }
}

pub fn eval_file(file_name: &str) -> String {
    let content = read_to_string(file_name).unwrap();
    let values = parse(&content.to_string());
    eval_all(&values)
        .iter()
        .map(|v| v.to_string())
        .collect::<Vec<String>>()
        .join(" ")
}

fn eval_all(values: &[Value]) -> Vec<Value> {
    let mut env = Environment::new();
    values.iter().map(|v| eval(v, &mut env)).collect()
}

fn eval(arg: &Value, env: &mut Environment) -> Value {
    match arg {
        Value::Def(var, value) => {
            env.bind(var, value);
            Value::Bool(true)
        }
        Value::Let(var, value, expr) => {
            env.bind(var, value);
            eval(expr, env)
        }
        Value::App(l, r) => {
            let result = apply(&eval(l, env), r);
            if is_reducible(&result) {
                eval(&result, env)
            } else {
                result
            }
        }
        Value::Sym(var) => env.bindings.get(var).unwrap_or(arg).clone(),
        other => other.clone(),
    }
}

fn is_reducible(result: &Value) -> bool {
    match result {
        Value::App(l, r) => match **l {
            Value::Lam(_, _) => true,
            _ => is_reducible(l) || is_reducible(r),
        },
        Value::Lam(_, _) => false,
        _ => false,
    }
}

fn apply(l: &Value, r: &Value) -> Value {
    if let Value::Lam(v, body) = l {
        subst(v, body, r)
    } else {
        Value::App(Box::new(l.clone()), Box::new(r.clone()))
    }
}

fn subst(var: &str, body: &Value, e: &Value) -> Value {
    match body {
        Value::Sym(x) if x == var => e.clone(),
        Value::Lam(x, b) if x == var => {
            let y = gensym();
            let bd = subst(x, b, &Value::Sym(y.clone()));
            Value::Lam(y, Box::new(bd))
        }
        Value::Lam(x, b) => Value::Lam(x.to_string(), Box::new(subst(var, b, e))),
        Value::App(l, r) => Value::App(Box::new(subst(var, l, e)), Box::new(subst(var, r, e))),
        other => other.clone(),
    }
}

fn gensym() -> String {
    let mut rng = rand::thread_rng();

    let n1: u8 = rng.gen();
    format!("x_{}", n1)
}

#[cfg(test)]
mod lambda_test {
    use crate::{eval, eval_all, parse, Environment, Value};

    fn parse1(string: &str) -> Value {
        parse(string).pop().unwrap()
    }

    fn eval1(value: &Value) -> Value {
        eval(value, &mut Environment::new())
    }

    #[test]
    fn evaluating_a_non_reducible_value_yields_itself() {
        let value = parse1("(foo 12)");
        assert_eq!(value, eval1(&value));
    }

    #[test]
    fn evaluating_application_on_an_abstraction_reduces_it() {
        let value = parse1("((lam x x) 12)");
        assert_eq!(Value::Num(12), eval1(&value));
    }

    #[test]
    fn substitution_occurs_within_abstraction_body() {
        let value = parse1("(((lam x (lam y x)) 13) 12)");
        assert_eq!(Value::Num(13), eval1(&value));
    }

    #[test]
    fn substitution_occurs_within_application_body() {
        let value = parse1("(((lam x (lam y (y x))) 13) 12)");
        assert_eq!(
            Value::App(Box::new(Value::Num(12)), Box::new(Value::Num(13))),
            eval1(&value)
        );
    }

    #[test]
    fn substitution_does_not_capture_free_variables() {
        let value = parse1("(((lam x (lam x x)) 13) 12)");
        assert_eq!(Value::Num(12), eval1(&value));
    }

    #[test]
    fn interpretation_applies_to_both_sides_of_application() {
        let value = parse1("((lam x x) ((lam x x) 12))");
        assert_eq!(Value::Num(12), eval1(&value));
    }

    #[test]
    fn reduction_is_applied_until_normal_form_is_reached() {
        let value = parse1("((((lam y (lam x (lam y (x y)))) 13) (lam x x)) 11)");
        assert_eq!(Value::Num(11), eval1(&value));
    }

    #[test]
    fn reduction_always_select_leftmost_outermost_redex() {
        // this should not terminate if we evaluate the rightmost redex first
        let value = parse1("((lam x 1) ((lam x (x x)) (lam x (x x))))");
        assert_eq!(Value::Num(1), eval1(&value));
    }

    #[test]
    fn defined_symbols_are_evaluated_to_their_definition() {
        let values = parse("(def foo 12)  foo");
        assert_eq!(vec![Value::Bool(true), Value::Num(12)], eval_all(&values));
    }

    #[test]
    fn let_expressions_bind_symbol_to_expression_in_environment() {
        let values = parse("(let (foo (lam x x))  (foo 12))");
        assert_eq!(vec![Value::Num(12)], eval_all(&values));
    }
}