use std::fmt;
use std::collections::HashMap;
use std::sync::Arc;
use std::convert::TryFrom;

use num::{BigRational, BigInt, One, ToPrimitive, FromPrimitive};

use maplit::hashmap;

#[cfg(feature = "compile")]
use serde::{Serialize, Deserialize};

use lazy_static::lazy_static;

use crate::{HashableMap, Error, Env, Pos, TokenType, Token, AST, RefTVal, ThreadHandle};

/// Function arguments for various types of functions.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum FnArgs {
    /// A way to call a function with `Token`s as arguments rather than their evaluated forms.
    Macro {
        /// The variables that the macro has access to.
        vars: HashableMap<String, RefTVal>,
        /// The position of the macro call.
        pos: Option<Pos>,
        /// The `Token`s captured by the macro.
        tokens: Vec<Token>,
    },
    /**
    The usual way to call a function.

    Note that this doesn't have `vars` since function values are evaluated beforehand.
    */
    Normal {
        /// A reference to the called function.
        this: Box<RefTVal>,
        /// The position of the function call.
        pos: Option<Pos>,
        /// A reference to the function argument list.
        args: RefTVal,
    },
}
/// A pair of updated environment vars and the evaluated value.
pub type FnReturn = (Option<HashMap<String, RefTVal>>, Result<RefTVal, Error>);

/// A function that is either called natively via Rust or run via an `AST`.
#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Callable {
    Native(fn(args: FnArgs) -> FnReturn),
    Value(RefTVal),
    AST(AST),
}
impl Callable {
    /**
    Returns the value of the function call in the given environment with the
    given `FnArgs`.
    */
    pub fn call<'a>(&self, env: &'a Env<'a>, args: FnArgs) -> FnReturn {
        match self {
            Callable::Native(fp) => fp(args),
            Callable::Value(rv) => (None, Ok(rv.clone())),
            Callable::AST(ast) => {
                // Setup Macro vars
                let mut nenv = Env::child(env);
                if let FnArgs::Macro { vars, pos, tokens } = &args {
                    nenv.set("env", &Value::from_env(&Env::from(vars.clone())).into());
                    nenv.set("pos", &match pos {
                        Some(p) => Value::from_pos(&p).into(),
                        None => Value::none().into(),
                    });
                    nenv.set("tokens", &Value::from_tokens(&tokens).into());
                }

                // Run function AST
                let (mut vars, val) = ast.run(&nenv);
                let val: Result<RefTVal, Error> = match val {
                    Err(Error::Control(s, cv)) if s == "return" => match cv {
                        Some(cv) => Ok((*cv).into()),
                        None => Err(Error::Script("Callable::AST::call(): failed to get return value".into(), ast.get_first_pos())),
                    },
                    _ => val,
                };

                // Handle Macro [vars, val]
                match args {
                    FnArgs::Macro { pos, .. } => {
                        match &val {
                            Ok(rv) => {
                                if let TVal { val: Value::List(l), .. } = rv.clone_out() {
                                    // Get vars
                                    if let Some(rv0) = l.get(0) {
                                        if let TVal { val: Value::Enum(_, e1), .. } = rv0.clone_out() {
                                            if &*e1.0 == "Some" {
                                                let hm = match e1.1.get(0) {
                                                    Some(rv) => {
                                                        if let Value::Struct(hm) = rv.clone_out().val {
                                                            hm
                                                        } else {
                                                            return (None, Err(Error::Script(format!("expected Struct for new env: {}", rv), pos)))
                                                        }
                                                    },
                                                    None => return (None, Err(Error::Script(format!("expected new env: {:?}", e1), pos))),
                                                };
                                                match &mut vars {
                                                    Some(vs) => vs.extend(hm),
                                                    None => vars = Some(hm.map),
                                                }
                                            }
                                        }
                                    }

                                    // Get val
                                    if let Some(rv1) = l.get(1) {
                                        if let TVal { val: Value::Enum(_, e2), .. } = rv1.clone_out() {
                                            let e2v = e2.1.get(0).cloned().unwrap_or_else(|| Value::none().into());
                                            match &*e2.0 {
                                                "Ok" => {
                                                    if let Value::List(l) = e2v.clone_out().val {
                                                        return (vars, Ok(l[0].clone()));
                                                    }
                                                    return (vars, Ok(e2v));
                                                },
                                                "Err" => {
                                                    let e2vv = e2v.clone_out().val;
                                                    let e = if let Value::List(l1) = e2vv {
                                                        if let Value::Enum(_, e) = l1[0].clone_out().val {
                                                            Some(e)
                                                        } else {
                                                            None
                                                        }
                                                    } else if let Value::Enum(_, e) = e2vv {
                                                        Some(e)
                                                    } else {
                                                        None
                                                    };
                                                    if let Some(e) = e {
                                                        // eprintln!("{:?} {:?}", l2, e.0);
                                                        let err = Value::Enum(Arc::new(vec![]), e).to_error();
                                                        // eprintln!("{:?}", err);
                                                        if let Some(err) = err {
                                                            return (vars, Err(err));
                                                        }
                                                    }
                                                    return (vars, Err(Error::Custom(e2v.clone_out())));
                                                },
                                                _ => {},
                                            }
                                        }

                                        return (vars, val);
                                    }
                                }
                            },
                            Err(m) => return (vars, Err(m.clone())),
                        }
                        return (None, Err(Error::Script(format!("failed to get FnReturn from user macro {:?}", val), None)));
                    },
                    _ => (None, val),
                }
            },
        }
    }
}

/**
A representation of a kind of `Value`. Most variants just represent the
corresponding `Value` variants.

The below associated functions return cloned `Arc`s to defaults.
*/
#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "compile", derive(Serialize, Deserialize))]
pub enum Type {
    /**
    Null type, only to be used internally. For external code, use an `Option`.
    */
    None,
    /**
    Used by generics to accept any type. This is available as `_` but
    generally prefer `generic` instead.
    */
    Any,

    Type,
    Reference,
    Number,
    String,

    List(Arc<Type>),
    Map(Arc<Type>, Arc<Type>),
    Enum(Arc<Vec<(String, Arc<Type>)>>),
    Struct(Arc<HashableMap<String, Arc<Type>>>),
    /**
    A pair of the underlying type and a map of generic parameter types.

    This doesn't correspond to a `Value` variant since the actual type it
    should act as is valid.
    */
    Generic(Arc<Type>, Arc<HashableMap<String, Arc<Type>>>),

    Function {
        args: Arc<Vec<(String, Arc<Type>)>>,
        ret: Arc<Type>,
    },
    Thread(Arc<Type>),
}
lazy_static! {
    pub(self) static ref EMPTY_MAP:   Arc<HashableMap<String, Arc<Type>>> = Arc::new(hashmap!{}.into());

    pub(self) static ref TYPE_NONE:   Arc<Type> = Arc::new(Type::None);
    pub(self) static ref TYPE_ANY:    Arc<Type> = Arc::new(Type::Any);
    pub(self) static ref TYPE_TYPE:   Arc<Type> = Arc::new(Type::Type);
    pub(self) static ref TYPE_REF:    Arc<Type> = Arc::new(Type::Reference);
    pub(self) static ref TYPE_NUMBER: Arc<Type> = Arc::new(Type::Number);
    pub(self) static ref TYPE_STRING: Arc<Type> = Arc::new(Type::String);

    static ref TYPE_LIST:   Arc<Type> = Arc::new(Type::List(Type::any()));
    static ref TYPE_MAP:    Arc<Type> = Arc::new(Type::Map(Type::any(), Type::any()));
    static ref TYPE_ENUM:   Arc<Type> = Arc::new(Type::Enum(Arc::new(vec![])));
    static ref TYPE_STRUCT: Arc<Type> = Arc::new(Type::Struct(Arc::clone(&EMPTY_MAP)));
    static ref TYPE_GENERIC: Arc<Type> = Arc::new(Type::Generic(Type::any(), Arc::clone(&EMPTY_MAP)));

    static ref TYPE_FUNCTION: Arc<Type> = Arc::new(Type::Function { args: Arc::new(vec![]), ret: Type::any() });
    static ref TYPE_THREAD: Arc<Type> = Arc::new(Type::Thread(Type::none()));
}
impl Type {
    #[must_use]
    pub fn none() -> Arc<Type> {
        Arc::clone(&TYPE_NONE)
    }
    #[must_use]
    pub fn any() -> Arc<Type> {
        Arc::clone(&TYPE_ANY)
    }

    #[must_use]
    pub fn ttype() -> Arc<Type> {
        Arc::clone(&TYPE_TYPE)
    }
    #[must_use]
    pub fn reference() -> Arc<Type> {
        Arc::clone(&TYPE_REF)
    }
    #[must_use]
    pub fn number() -> Arc<Type> {
        Arc::clone(&TYPE_NUMBER)
    }
    #[must_use]
    pub fn string() -> Arc<Type> {
        Arc::clone(&TYPE_STRING)
    }

    #[must_use]
    pub fn list() -> Arc<Type> {
        Arc::clone(&TYPE_LIST)
    }
    #[must_use]
    pub fn map() -> Arc<Type> {
        Arc::clone(&TYPE_MAP)
    }
    #[must_use]
    pub fn tenum() -> Arc<Type> {
        Arc::clone(&TYPE_ENUM)
    }
    #[must_use]
    pub fn tstruct() -> Arc<Type> {
        Arc::clone(&TYPE_STRUCT)
    }
    #[must_use]
    pub fn generic() -> Arc<Type> {
        Arc::clone(&TYPE_GENERIC)
    }

    #[must_use]
    pub fn function() -> Arc<Type> {
        Arc::clone(&TYPE_FUNCTION)
    }
    #[must_use]
    pub fn thread() -> Arc<Type> {
        Arc::clone(&TYPE_THREAD)
    }

    /**
    Check whether two base types are the same. Purposely doesn't check
    subtypes.
    */
    pub fn equiv<T: AsRef<Type>>(&self, other: T) -> bool {
        let other = other.as_ref();
        // TODO do proper type checking
        if matches!(self, Type::Any) || matches!(other, Type::Any) {
            return true;
        }

        match self {
            Type::None => matches!(other, Type::None),
            Type::Any => matches!(other, Type::Any),
            Type::Type => matches!(other, Type::Type),
            Type::Reference => matches!(other, Type::Reference),
            Type::Number => matches!(other, Type::Number),
            Type::String => matches!(other, Type::String),

            Type::List(_l1) => matches!(other, Type::List(_l2)),
            Type::Map(_mk1, _mv1) => matches!(other, Type::Map(_mk2, _mv2)),
            Type::Enum(_es1) => matches!(other, Type::Enum(_es2)),
            Type::Struct(_ss1) => matches!(other, Type::Struct(_ss2)),
            Type::Generic(_gu1, _gp1) => matches!(other, Type::Generic(_gu2, _gp2)),

            Type::Function { args: _args1, ret: _ret1 } => matches!(other, Type::Function { args: _args2, ret: _ret2 }),
            Type::Thread(_ret1) => matches!(other, Type::Thread(_ret2)),
        }
    }
}
impl fmt::Display for Type {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Type::None => write!(f, "None"),
            Type::Any => write!(f, "Any"),
            Type::Type => write!(f, "Type"),
            Type::Reference => write!(f, "Reference"),
            Type::Number => write!(f, "Number"),
            Type::String => write!(f, "String"),

            Type::List(t) => write!(f, "List[{}]", *t),
            Type::Map(k, v) => write!(f, "Map[{}, {}]", *k, *v),
            Type::Enum(es) => write!(f, "Enum{:?}", es.iter().map(|(k, _)| k)),
            Type::Struct(ss) => write!(f, "Struct{:?}", ss),
            Type::Generic(gu, gp) => write!(f, "Generic[{}, {:?}]", gu, gp),

            Type::Function { args, ret } => write!(f, "Function[{:?} -> {}]", args, ret),
            Type::Thread(ret) => write!(f, "Thread[{}]", ret),
        }
    }
}
impl TryFrom<&str> for Type {
    type Error = Error;
    fn try_from(s: &str) -> Result<Self, Error> {
        Ok(match s {
            "None" => Type::None,
            "Any" => Type::Any,
            "Type" => Type::Type,
            "Number" => Type::Number,
            "String" => Type::String,

            // TODO add complex type support
            "List" => Type::List(Self::none()),
            "Map" => Type::Map(Self::none(), Self::none()),
            "Enum" => Type::Enum(Arc::new(vec![])),
            "Struct" => Type::Struct(Arc::new(hashmap!{}.into())),

            "Function" => Type::Function { args: Arc::new(vec![]), ret: Self::none()},

            _ => return Err(Error::Script(format!("Type::try_from invalid typename: {}", s), Option::None)),
        })
    }
}

/// A representation of any valid value in a script.
#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "compile", derive(Serialize, Deserialize))]
pub enum Value {
    /// A `Type` with subtype values.
    Type(Arc<Type>, Arc<HashableMap<String, RefTVal>>),
    /// A reference to another value.
    Reference(RefTVal),
    /// Any rational number.
    Number(BigRational),
    /// Any UTF8 string.
    String(String),

    /// An array of values.
    List(Vec<RefTVal>),
    /// A one-to-one mapping of values. Any value is valid for keys.
    Map(HashableMap<RefTVal, RefTVal>),
    /**
    A sum type represented by the possible variants and the specific variant
    name and its value.

    Enum comparison is currently done via string comparison which should change
    in the future.
    */
    Enum(Arc<Vec<(String, Arc<Type>)>>, Box<(String, Vec<RefTVal>)>), // TODO change es to Arc<Type>
    /**
    A structure containing fields and their values.

    Methods may be defined just like any other values, however there is no
    inheritance. Use composition via `trait` instead.
    */
    Struct(HashableMap<String, RefTVal>),

    /**
    Any `Callable` along with its argument types and the associated flattened
    environment.
    */
    Function {
        args: Arc<Vec<(String, Arc<Type>)>>,
        vars: HashableMap<String, RefTVal>,
        body: Callable, // custom serde impl in runnable.rs
    },
    /**
    A `ThreadHandle` of a running thread. May be joined for `FnReturn`.
    */
    Thread(ThreadHandle),
}
lazy_static! {
    static ref ENUM_TOKEN_TYPE: Arc<Vec<(String, Arc<Type>)>> = Arc::new(vec![
        ("Identifier".into(), Type::none()),
        ("Number".into(), Type::none()),
        ("String".into(), Type::none()),
        ("Container".into(), Type::none()),
        ("Symbol".into(), Type::none()),
    ]);
    static ref ENUM_AST: Arc<Vec<(String, Arc<Type>)>> = Arc::new(vec![
        ("Macro".into(), Type::none()),
        ("Container".into(), Type::none()),
        ("Operator".into(), Type::none()),
        ("Value".into(), Type::none()),
        ("Empty".into(), Type::none()),
    ]);
}
impl Value {
    pub(crate) fn none() -> Self {
        Value::Type(Type::none(), HashableMap::arc())
    }

    /**
    Clones itself such that any contained `RefTVal`s no longer reference their
    original.
    */
    pub(crate) fn deep_clone(&self, attr: bool) -> Value {
        match self {
            Value::Type(t, ts) => Value::Type(Arc::clone(&t), Arc::new(ts.deep_clone(attr))),
            Value::Reference(rv) => Value::Reference(rv.deep_clone(attr)),
            Value::Number(_) | Value::String(_) => self.clone(),

            Value::List(l) => Value::List(l.iter().map(|v| v.deep_clone(attr)).collect()),
            Value::Map(hm) => Value::Map(hm.deep_clone(attr)),
            Value::Enum(es, e) => Value::Enum(es.clone(), Box::new((e.0.clone(), e.1.clone().iter().map(|v| v.deep_clone(attr)).collect()))),
            Value::Struct(st) => Value::Struct(st.deep_clone(attr)),

            Value::Function { args, vars, body } => Value::Function {
                args: args.clone(),
                vars: vars.deep_clone(attr),
                body: body.clone(),
            },
            Value::Thread(th) => Value::Thread(th.clone()),
        }
    }

    pub(crate) fn from_pos(pos: &Pos) -> Self {
        Value::Struct(hashmap!{
            "filename".into() => Value::from(&*pos.filename).into(),
            "line".into() => Value::from(pos.line).into(),
            "col".into() => Value::from(pos.col).into(),
        }.into())
    }
    pub(crate) fn from_token_type(ttype: &TokenType) -> Self {
        let tt: String = match ttype {
            TokenType::Identifier => "Identifier".into(),
            TokenType::Number => "Number".into(),
            TokenType::String => "String".into(),
            TokenType::Container => "Container".into(),
            TokenType::Symbol => "Symbol".into(),
            TokenType::Comment => "Comment".into(),
        };
        Value::Enum(Arc::clone(&ENUM_TOKEN_TYPE), Box::from((tt, vec![])))
    }
    pub(crate) fn from_token(token: &Token) -> Self {
        Value::Struct(hashmap!{
            "ttype".into() => Value::from_token_type(&token.ttype).into(),
            "pos".into() => Value::from_pos(&token.pos).into(),
            "data".into() => Value::from(&*token.data).into(),
        }.into())
    }
    pub(crate) fn from_tokens(tokens: &[Token]) -> Self {
        tokens.iter()
            .map(|t| Value::from_token(t))
            .collect::<Vec<Value>>()
            .into()
    }

    pub(crate) fn from_env<'a>(env: &Env<'a>) -> Self {
        let p: HashableMap<RefTVal, RefTVal> = match &env.parent {
            Some(p) => Env::flatten(p).vars.iter()
                .map(|(k, v)| (Value::String(k.clone()).into(), v.clone()))
                .collect(),
            None => hashmap!{}.into(),
        };
        let vs: HashableMap<RefTVal, RefTVal> = env.vars.iter()
            .map(|(k, v)| (Value::String(k.clone()).into(), v.clone()))
            .collect();
        Value::Struct(HashableMap::from(hashmap!{
            "parent".into() => Value::Map(p).into(),
            "vars".into() => Value::Map(vs).into(),
        }))
    }
    pub(crate) fn from_ast(ast: &AST) -> Self {
        let (at, av): (String, Value) = match ast {
            AST::Macro { tokens } => ("Macro".into(), Value::Struct(hashmap!{
                "tokens".into() => Value::from_tokens(tokens).into(),
            }.into())),
            AST::Container { token, children } => ("Container".into(), Value::Struct(hashmap!{
                "token".into() => Value::from_token(token).into(),
                "children".into() => Value::List(children.iter()
                    .map(|c| Value::from_ast(c).into())
                    .collect()
                ).into(),
            }.into())),
            AST::Operator { token, lhs, rhs } => ("Operator".into(), Value::Struct(hashmap!{
                "token".into() => Value::from_token(token).into(),
                "lhs".into() => Value::from_ast(lhs).into(),
                "rhs".into() => Value::from_ast(rhs).into(),
            }.into())),
            AST::Value { token } => ("Value".into(), Value::Struct(hashmap!{
                "token".into() => Value::from_token(token).into(),
            }.into())),
            AST::Empty => ("Empty".into(), Value::none()),
        };
        Value::Enum(Arc::clone(&ENUM_AST), Box::from((at, vec![av.into()])))
    }

    pub(crate) fn from_option(o: &Option<RefTVal>) -> Self {
        let es = Arc::new(vec![
            ("Some".into(), Type::any()),
            ("None".into(), Type::none()),
        ]);
        match o {
            Some(v) => Value::Enum(es, Box::new(("Some".into(), vec![v.clone()]))),
            None => Value::Enum(es, Box::new(("None".into(), vec![]))),
        }
    }
    pub(crate) fn from_result(r: &Result<RefTVal, Error>) -> Self {
        let es = Arc::new(vec![
            ("Ok".into(), Type::any()),
            ("Err".into(), Type::any()),
        ]);
        match r {
            Ok(v) => Value::Enum(es, Box::new(("Ok".into(), vec![v.clone()]))),
            Err(m) => Value::Enum(es,
                Box::new(("Err".into(), vec![Value::from_error(&m).into()]),
            )),
        }
    }
    pub(crate) fn from_result_reftval(r: &Result<RefTVal, RefTVal>) -> Self {
        let es = Arc::new(vec![
            ("Ok".into(), Type::any()),
            ("Err".into(), Type::any()),
        ]);
        match r {
            Ok(v) => Value::Enum(es, Box::new(("Ok".into(), vec![v.clone()]))),
            Err(m) => Value::Enum(es, Box::new(("Err".into(), vec![m.clone()]))),
        }
    }
    pub(crate) fn from_error(e: &Error) -> Self {
        Value::Enum(
            Arc::new(vec![
                ("ArgumentError".into(), Type::string()),
                ("ParseError".into(), Type::list()),
                ("ScriptError".into(), Type::list()),
                ("ControlError".into(), Type::list()),
                ("CustomError".into(), Type::any()),
            ]),
            Box::new(match e {
                Error::Argument(m) => ("ArgumentError".into(), vec![Value::String(m.clone()).into()]),
                Error::Parse(m, p) => ("ParseError".into(), vec![
                    Value::String(m.clone()).into(),
                    Value::from_option(&p.as_ref().map(|p| Value::from_pos(&p).into())).into(),
                ]),
                Error::Script(m, p) => ("ScriptError".into(), vec![
                    Value::String(m.clone()).into(),
                    Value::from_option(&p.as_ref().map(|p| Value::from_pos(&p).into())).into(),
                ]),
                Error::Control(m, v) => ("ControlError".into(), vec![
                    Value::String(m.clone()).into(),
                    v.as_ref().map(|v| (**v).clone().into()).unwrap(),
                ]),
                Error::Custom(v) => ("CustomError".into(), vec![v.clone().into()]),
            }),
        )
    }
    pub(crate) fn to_error(&self) -> Option<Error> {
        if let Value::Enum(_, e) = self {
            match &*e.0 {
                "ArgumentError" => match &e.1.get(0) {
                    Some(rv) => Some(Error::Argument(rv.clone_out().val.to_string())),
                    _ => None,
                },
                "ParseError" => match &e.1.get(1) {
                    Some(rv1) => match rv1.clone_out().val {
                        Value::Enum(_, e2) => {
                            match &*e2.0 {
                                "Some" => {
                                    match &e2.1.get(0) {
                                        Some(rv0) => {
                                            let pos = Pos::from_value(&rv0.clone_out().val);
                                            Some(Error::Parse(e.1[0].clone_out().val.to_string(), pos))
                                        },
                                        _ => None,
                                    }
                                },
                                _ => None,
                            }
                        },
                        _ => None,
                    },
                    _ => None,
                },
                "ScriptError" => match &e.1.get(1) {
                    Some(rv1) => match rv1.clone_out().val {
                        Value::Enum(_, e2) => {
                            match &*e2.0 {
                                "Some" => {
                                    match &e2.1.get(0) {
                                        Some(rv0) => {
                                            let pos = Pos::from_value(&rv0.clone_out().val);
                                            Some(Error::Script(e.1[0].clone_out().val.to_string(), pos))
                                        },
                                        _ => None,
                                    }
                                },
                                _ => None,
                            }
                        },
                        _ => None,
                    },
                    _ => None,
                },
                "ControlError" => match &e.1.get(0) {
                    Some(rv) => Some(Error::Control(rv.clone_out().val.to_string(), e.1.get(1).cloned().map(|v| Box::new(v.clone_out())))),
                    _ => None,
                },
                "CustomError" => match &e.1.get(0) {
                    Some(rv) => Some(Error::Custom(rv.clone_out())),
                    _ => None,
                },
                _ => None,
            }
        } else {
            None
        }
    }
}
impl From<usize> for Value {
    fn from(n: usize) -> Self {
        Value::Number(BigRational::from_usize(n).expect("expected usize to fit in BigRational"))
    }
}
impl From<&str> for Value {
    fn from(s: &str) -> Self {
        Value::String(s.into())
    }
}
impl From<Vec<Value>> for Value {
    fn from(vs: Vec<Value>) -> Self {
        let mut tvs = vec![];
        for v in vs {
            tvs.push(v.into());
        }
        Value::List(tvs)
    }
}
impl fmt::Debug for Value {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Value::Type(t, _) => {
                write!(f, "Type[{}]", t)
                // write!(f, "{}{:?}", t, ts.keys())
            },
            Value::Reference(rv) => {
                write!(f, "Ref[{:?}]", rv)
            },
            Value::Number(r) => {
                if r.denom() == &BigInt::one() {
                    write!(f, "{}", r.numer())
                } else {
                    write!(f, "{}", r.to_f64().ok_or(std::fmt::Error)?)
                }
            },
            Value::String(s) => {
                write!(f, "{}", s)
            },

            Value::List(l) => write!(f, "{:?}", {
                l.iter()
                    .map(|x| x.clone_out().val)
                    .collect::<Vec<Value>>()
            }),
            Value::Map(m) => write!(f, "{:?}", {
                m.iter()
                    .map(|(k, v)| (k.clone_out().val, v.clone_out().val))
                    .collect::<HashMap<Value, Value>>()
            }),
            Value::Enum(_, e) => write!(f, "Enum Variant {{{}: {:?}}}", &e.0, &e.1),
            Value::Struct(st) => write!(f, "Struct {:?}", {
                st.iter()
                    .map(|(n, v)| (n, v.clone_out().val))
                    .collect::<HashMap<&std::string::String, Value>>()
            }),

            Value::Function { args, body, .. } => {
                match body {
                    Callable::Native(fp) => write!(f, "Function {{ args: {:?}, body: Native({:?}), .. }}", args, fp),
                    Callable::Value(rv) => write!(f, "Function {{ args: {:?}, body: Value({}), .. }}", args, rv),
                    Callable::AST(_) => write!(f, "Function {{ args: {:?}, .. }}", args),
                }
            },
            Value::Thread(ThreadHandle { body, .. }) => {
                match body {
                    Callable::Native(fp) => write!(f, "Thread {{ body: Native({:?}), .. }}", fp),
                    Callable::Value(rv) => write!(f, "Function {{ body: Value({}), .. }}", rv),
                    Callable::AST(_) => write!(f, "Thread {{ .. }}"),
                }
            },
        }
    }
}
impl fmt::Display for Value {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        <Self as fmt::Debug>::fmt(self, f)
    }
}

/// A `Type`-`Value` pair along with an attribute map.
#[derive(Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "compile", derive(Serialize, Deserialize))]
pub struct TVal {
    pub ttype: Arc<Type>,
    pub attr: HashableMap<String, RefTVal>,
    pub val: Value,
}
impl TVal {
    /**
    Clones itself such that any contained `RefTVal`s no longer reference their
    original.
    */
    #[must_use]
    pub fn deep_clone(&self, attr: bool) -> TVal {
        TVal {
            ttype: Arc::clone(&self.ttype),
            attr: self.attr.deep_clone(attr),
            val: self.val.deep_clone(attr),
        }
    }
}
impl From<String> for TVal {
    fn from(s: String) -> Self {
        TVal {
            ttype: Type::string(),
            attr: hashmap!{}.into(),
            val: Value::String(s),
        }
    }
}
impl From<Value> for TVal {
    fn from(val: Value) -> Self {
        use self::Type as T;
        use Value as V;
        match &val {
            V::Type(_, _) => TVal {
                ttype: T::ttype(),
                attr: hashmap!{}.into(),
                val,
            },
            V::Reference(_) => TVal {
                ttype: T::reference(),
                attr: hashmap!{}.into(),
                val,
            },
            V::Number(_) => TVal {
                ttype: T::number(),
                attr: hashmap!{}.into(),
                val,
            },
            V::String(_) => TVal {
                ttype: T::string(),
                attr: hashmap!{}.into(),
                val,
            },

            V::List(l) => TVal {
                ttype: Arc::new(T::List({
                    if let Some(a) = l.first() {
                        Arc::clone(&a.clone_out().ttype)
                    } else {
                        T::none()
                    }
                })),
                attr: hashmap!{}.into(),
                val,
            },
            V::Map(m) => TVal {
                ttype: Arc::new(if let Some((k, v)) = m.iter().next() {
                    T::Map(Arc::clone(&k.clone_out().ttype), Arc::clone(&v.clone_out().ttype))
                } else {
                    T::Map(T::none(), T::none())
                }),
                attr: hashmap!{}.into(),
                val,
            },
            V::Enum(es, ..) => TVal {
                ttype: Arc::new(T::Enum(Arc::clone(&es))),
                attr: hashmap!{}.into(),
                val,
            },
            V::Struct(ss) => TVal {
                ttype: Arc::new(T::Struct({
                    let mut sts = hashmap!{};
                    for s in &ss.map {
                        sts.insert(s.0.clone(), Arc::clone(&s.1.clone_out().ttype));
                    }
                    Arc::new(sts.into())
                })),
                attr: hashmap!{}.into(),
                val,
            },

            V::Function { args, .. } => TVal {
                ttype: Arc::new(T::Function {
                    args: Arc::clone(&args),
                    ret: T::none(), // TODO find return type
                }),
                attr: hashmap!{}.into(),
                val,
            },
            V::Thread(_) => TVal {
                ttype: Arc::new(T::Thread(T::none())),
                attr: hashmap!{}.into(),
                val,
            },
        }
    }
}
impl fmt::Debug for TVal {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let attr = if self.attr.is_empty() {
            "".to_string()
        } else {
            format!(" @ {:?}", self.attr)
        };
        match &self.val {
            Value::String(s) => write!(f, "<\"{}\": {}{}>", s.replace('\\', r#"\\"#).replace('"', r#"\""#), self.ttype, attr),
            Value::Function { .. } => write!(f, "<{}{}>", self.ttype, attr),
            _ => write!(f, "<{}: {}{}>", self.val, self.ttype, attr),
        }
    }
}
impl fmt::Display for TVal {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        <Self as fmt::Debug>::fmt(self, f)
    }
}

pub trait VecMap<T> {
    fn contains_key(&self, k: &str) -> bool;
    fn get(&self, k: &str) -> Option<(String, T)>;
    fn set(&mut self, k: &str, v: T) -> Option<(String, T)>;
}
impl<T> VecMap<T> for Vec<(String, T)>
where
    T: Clone,
{
    fn contains_key(&self, k: &str) -> bool {
        self.iter()
            .any(|(s, _v)| s == k)
    }
    fn get(&self, k: &str) -> Option<(String, T)> {
        for (s, v) in self {
            if s == k {
                return Some((s.clone(), v.clone()));
            }
        }
        None
    }
    fn set(&mut self, k: &str, nv: T) -> Option<(String, T)> {
        for (s, v) in self.iter_mut() {
            if s == k {
                let tv = v.clone();
                *v = nv;
                return Some((k.to_string(), tv));
            }
        }
        self.push((k.to_string(), nv));
        None
    }
}

pub fn match_pat(tv: &RefTVal, pat: &AST, pos: Option<Pos>) -> Result<Option<HashMap<String, RefTVal>>, Error> {
    let enumval = match &tv.clone_out().val {
        Value::Reference(rv) => return match_pat(rv, pat, pos),
        Value::Enum(_es, e) => e.clone(),
        _ => return Err(Error::Script(format!("match_pat failed: not an enum {}", tv), pos)),
    };

    match pat {
        AST::Operator { token, lhs, rhs } if token.data == "(" => {
            if let AST::Value { token: ltoken } = &**lhs {
                if ltoken.data == enumval.0 {
                    let mut hm: HashMap<String, RefTVal> = hashmap!{};
                    match &**rhs {
                        AST::Container { token: rtoken, children } if rtoken.data == "(" => {
                            for (c, ev) in children.iter().zip(enumval.1) {
                                match c {
                                    AST::Value { token: ctoken } => {
                                        hm.insert(ctoken.data.clone(), ev.clone());
                                    },
                                    _ => return Err(Error::Script(format!("match_pat failed: invalid RHS child {:?}", c), pos)),
                                }
                            }
                        },
                        _ => return Err(Error::Script(format!("match_pat failed: invalid RHS for {}", ltoken.data), pos)),
                    }
                    return Ok(Some(hm));
                }
            }
        },
        AST::Value { token } => {
            if token.data == enumval.0 || token.data == "_" {
                return Ok(None);
            }
        },
        _ => {},
    }
    Err(Error::Script(format!(
        "match_pat failed for {} against {:?}",
        tv,
        pat.get_first_token().unwrap_or(Token {
            ttype: TokenType::Identifier,
            pos: pos.clone().unwrap_or(Pos {
                filename: "<match>".into(),
                line: 0,
                col: 0,
            }),
            data: "EMPTY".into(),
        }).data
    ), pos))
}