borrow.rs

// boorrow

use std::collections::{HashMap, VecDeque};

use crate::ast::*;
use crate::env::*;

type Id = String;

#[derive(Debug, Clone)]
enum Val {
    Num(i32),
    Bool(bool),
    Uninitialized,
    Unit,
    Ref(Id),
    RefMut(Id),
}

type IdVal = HashMap<Id, (bool, Val)>;

#[derive(Debug)]
struct Mem(VecDeque<IdVal>);

impl Mem {
    fn new() -> Self {
        Mem(VecDeque::new())
    }

    fn get(&self, id: String) -> Option<&Val> {
        self.0.iter().find_map(|hm| match hm.get(id.as_str()) {
            Some((_, v)) => Some(v), // always ok to go from mut to non mut
            _ => None,
        })
    }

    fn get_mut(&mut self, id: String) -> Option<&mut Val> {
        self.0
            .iter_mut()
            .find_map(|hm| match hm.get_mut(id.as_str()) {
                Some((true, v)) => Some(v), // a mut reference
                Some((_, v)) => {
                    match v {
                        Val::Uninitialized => Some(v), // an uninitialized
                        Val::RefMut(_) => {
                            // a ref mut
                            println!("get &mut {:?}", v);
                            Some(v)
                        }
                        _ => panic!("cannot access as mutable"),
                    }
                }
                _ => None,
            })
    }

    fn new_id(&mut self, id: String, is_mut: bool) {
        let hm = self.0.front_mut().unwrap();
        println!("insert id {:?}, in scope {:?}", id, hm);

        hm.insert(id, (is_mut, Val::Uninitialized));
    }

    fn update(&mut self, id: String, val: Val) {
        // println!("before mem {:?}", self);
        match self.get_mut(id.clone()) {
            Some(v_ref) => {
                println!("found");
                *v_ref = val;
            }
            None => {
                panic!("variable not found");
            }
        };
        // println!("after mem {:?}", self);
    }

    fn push_empty_scope(&mut self) {
        self.0.push_front(HashMap::new());
    }

    fn push_param_scope(&mut self, args: IdVal) {
        self.0.push_front(args)
    }

    fn pop_scope(&mut self) {
        self.0.pop_front();
    }
}

fn eval_infix(l: Val, op: &Op, r: Val) -> Val {
    match (l, op, r) {
        // Operations on Num
        (Val::Num(l), op, Val::Num(r)) => match op {
            // arithmetic operations on Num
            Op::Add => Val::Num(l + r),
            Op::Sub => Val::Num(l - r),
            Op::Mul => Val::Num(l * r),
            Op::Div => Val::Num(l / r),
            // comparisons
            Op::Eq => Val::Bool(l == r),
            Op::Neq => Val::Bool(l != r),
            Op::Less => Val::Bool(l < r),
            Op::LessEq => Val::Bool(l <= r),
            Op::Greater => Val::Bool(l > r),
            Op::GreaterEq => Val::Bool(l >= r),
            _ => panic!("expression evaluation error"),
        },
        // boolean
        (Val::Bool(l), op, Val::Bool(r)) => Val::Bool(match op {
            Op::And => l && r,
            Op::Or => l || r,
            Op::Eq => l == r,
            _ => panic!("expression evaluation error"),
        }),
        _ => panic!("expression evaluation error"),
    }
}

fn eval_prefix(op: &Op, r: Val) -> Val {
    match (op, r) {
        // Operations on Num
        (op, Val::Num(r)) => match op {
            // arithmetic operations on Num
            Op::Sub => Val::Num(-r),
            Op::Add => Val::Num(r),
            _ => panic!("expression evaluation error"),
        },
        // boolean
        (op, Val::Bool(r)) => match op {
            Op::Not => Val::Bool(!r),
            _ => panic!("expression evaluation error"),
        },
        // Unint
        _ => panic!("expression evaluation error"),
    }
}

fn eval_expr(e: &Expr, m: &mut Mem, fn_env: &FnEnv) -> Val {
    println!("eval_expr {}", e);
    match e {
        Expr::Num(i) => Val::Num(*i),
        Expr::Bool(b) => Val::Bool(*b),
        // Expr::As(_, _) => {}
        Expr::Infix(l, op, r) => {
            let l = eval_expr(l, m, fn_env);
            let r = eval_expr(r, m, fn_env);
            eval_infix(l, op, r)
        }
        Expr::Prefix(op, r) => {
            let r = eval_expr(r, m, fn_env);
            eval_prefix(op, r)
        }
        Expr::Id(id) => match m.get(id.to_owned()) {
            Some(v) => v.clone(),
            None => panic!("identifier not found {:?}", id),
        },
        Expr::Ref(e) => match &**e {
            Expr::Id(id) => match m.get(id.to_owned()) {
                Some(_) => Val::Ref(id.to_owned()),
                None => panic!("identifier not found {:?}", id),
            },
            _ => panic!("ref of non identifier"),
        },
        Expr::RefMut(e) => match &**e {
            Expr::Id(id) => match m.get(id.to_owned()) {
                Some(_) => Val::RefMut(id.to_owned()),
                None => panic!("identifier not found {:?}", id),
            },
            _ => panic!("ref on non identifier"),
        },
        Expr::DeRef(e) => {
            println!("deref e {:?}", e);

            let ev = eval_expr(e, m, fn_env);
            println!("ev {:?}", ev);

            match ev {
                Val::Ref(id) => eval_expr(&Expr::Id(id), m, fn_env),
                Val::RefMut(id) => eval_expr(&Expr::Id(id), m, fn_env),
                _ => panic!("cannot deref"),
            }
        }
        Expr::Call(id, ee) => {
            println!("call {}", id);
            let args: Vec<Val> = ee.0.iter().map(|e| eval_expr(e, m, fn_env)).collect();

            eval_fn(id, &args, m, fn_env)
        }
        _ => {
            unimplemented!();
        }
    }
}

fn eval_left_expr(e: &Expr, m: &Mem, fn_env: &FnEnv) -> Id {
    println!("eval_left_expr {}", e);
    match e {
        Expr::Id(id) => id.to_owned(),

        Expr::DeRef(e) => {
            println!("eval_left deref e {:?}", e);

            let ev = eval_left_expr(e, m, fn_env);
            println!("eval_left {:?}", ev);

            match m.get(ev) {
                Some(Val::Ref(id)) => {
                    println!("Ref id {}", id);
                    id.clone()
                }
                Some(Val::RefMut(id)) => {
                    println!("RefMut id {}", id);
                    id.clone()
                }
                _ => panic!("deref failed"),
            }
        }
        _ => panic!("illegal left hand expression"),
    }
}

fn eval_stmts(stmts: &Stmts, m: &mut Mem, fn_env: &FnEnv) -> Val {
    let ss = &stmts.stmts;

    m.push_empty_scope();

    let mut stmt_val = Val::Unit;

    for s in ss {
        println!("s {}", s);
        println!("m {:?}", m);
        stmt_val = match s {
            // Id, is_mut, Option<Type>, Option<Box<Expr>
            Stmt::Let(id, is_mut, _, o_expr) => {
                println!("let");
                m.new_id(id.to_owned(), *is_mut);
                match o_expr {
                    Some(e) => {
                        let r = eval_expr(e, m, fn_env);
                        println!("r {:?}", r);
                        m.update(id.to_owned(), r);
                        Val::Unit
                    }
                    _ => Val::Unit,
                }
            }
            Stmt::Assign(ev, e) => {
                println!("assign");
                match &**ev {
                    Expr::Id(id) => {
                        let v = eval_expr(e, m, fn_env);
                        m.update(id.to_owned(), v)
                    }
                    _ => {
                        let lv = eval_left_expr(ev, m, fn_env);
                        println!("lv {:?}", lv);
                        let v = eval_expr(e, m, fn_env);
                        m.update(lv, v)
                    }
                };
                Val::Unit
            }
            Stmt::While(e, while_block) => {
                println!("while");
                while match eval_expr(e, m, fn_env) {
                    Val::Bool(b) => b,
                    _ => panic!("non boolean condition"),
                } {
                    eval_stmts(while_block, m, fn_env);
                }
                Val::Unit
            }
            Stmt::If(e, then_block, op_else_block) => {
                println!("if");
                // println!("scope before {}", m);
                match (eval_expr(e, m, fn_env), op_else_block) {
                    (Val::Bool(true), _) => eval_stmts(then_block, m, fn_env),
                    (Val::Bool(false), Some(else_block)) => eval_stmts(else_block, m, fn_env),
                    (Val::Bool(_), _) => Val::Uninitialized, // this should never happen if value used
                    _ => panic!("non boolean condition"),
                }
            }
            Stmt::Expr(e) => {
                println!("expr");
                eval_expr(e, m, fn_env)
            }
            Stmt::Block(block) => {
                println!("block");
                eval_stmts(block, m, fn_env)
            }
            Stmt::Semi => Val::Unit,
        }
    }
    m.pop_scope();
    if stmts.trailing_semi {
        Val::Unit
    } else {
        println!("statements with return value {:?}", stmt_val);
        stmt_val
    }
}

fn eval_fn(id: &str, args: &Vec<Val>, m: &mut Mem, fn_env: &FnEnv) -> Val {
    if let Some(fn_decl) = fn_env.get(id) {
        println!("f id {:?}, {:?}", id, fn_decl.params);

        let p_id: &Vec<(bool, String)> = &fn_decl
            .params
            .0
            .iter()
            .map(|param| (param.is_mut, param.id.to_owned()))
            .collect();

        let p_id_arg: Vec<(&(bool, String), &Val)> = p_id.iter().zip(args).collect();
        let p_id_arg: IdVal = p_id_arg
            .into_iter()
            .map(|(s, v)| (s.1.clone(), (s.0, v.clone())))
            .collect();

        println!("args {:?}", args);
        println!("p_id_arg {:?}", &p_id_arg);

        m.push_param_scope(p_id_arg);
        let ret = eval_stmts(&fn_decl.body, m, fn_env);
        println!("mem {:?}, ret {:?}", m, ret);
        m.pop_scope();
        ret
    } else {
        panic!("function not found");
    }
}

pub fn eval_prog(file_name: &str) {
    let p = crate::read_file::parse(file_name);
    println!("prog \n{}", p);

    let fn_env = new_fn_env(&p.fn_decls);
    let args: Vec<Val> = Vec::new();
    let mut m = Mem::new();

    eval_fn("main", &args, &mut m, &fn_env);
}

#[test]
fn test_deref() {
    let mut m: Mem = Mem::new();
    let mut hm = IdVal::new();

    hm.insert("a".to_string(), (false, Val::Num(7)));
    hm.insert("b".to_string(), (false, Val::Ref("a".to_string())));
    hm.insert("c".to_string(), (false, Val::Ref("b".to_string())));
    m.push_param_scope(hm);
    println!("mem {:?}", m);
    let e: Expr = Expr::Id("a".to_string());
    let v = eval_expr(&e, &mut m, &FnEnv::new());
    println!("v {:?}", v);

    let e: Expr = Expr::DeRef(Box::new(Expr::Id("b".to_string())));
    let v = eval_expr(&e, &mut m, &FnEnv::new());
    println!("v {:?}", v);

    let e: Expr = Expr::DeRef(Box::new(Expr::Id("c".to_string())));
    let v = eval_expr(&e, &mut m, &FnEnv::new());
    println!("v {:?}", v);

    let e: Expr = Expr::DeRef(Box::new(Expr::DeRef(Box::new(Expr::Id("c".to_string())))));
    let v = eval_expr(&e, &mut m, &FnEnv::new());
    println!("v {:?}", v);
}