// TODO:
// * [ ] ensure `or` and `and` never get passed by reference
// * [ ] ensure no placeholder in `or` and `and` args
// * [ ] ensure loops have fixed arity (no splats)
// * [ ] ensure fn pattern splats are always highest (and same) arity

use crate::ast::{Ast, StringPart};
use crate::spans::{Span, Spanned};
use crate::value::{Key, Value};
use std::collections::{HashMap, HashSet};

#[derive(Clone, Debug, PartialEq)]
pub struct VErr<'a> {
    pub msg: String,
    pub span: &'a Span,
    pub input: &'static str,
    pub src: &'static str,
}

impl<'a> VErr<'a> {
    pub fn new(msg: String, span: &'a Span, input: &'static str, src: &'static str) -> VErr<'a> {
        VErr {
            msg,
            span,
            input,
            src,
        }
    }
}

#[derive(Clone, Debug, PartialEq)]
struct VStatus {
    tail_position: bool,
    in_loop: bool,
    loop_arity: u8,
    last_term: bool,
    has_placeholder: bool,
    used_bindings: Vec<String>,
}

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub enum Arity {
    Fixed(u8),
    Splat(u8),
}

#[derive(Clone, Debug, PartialEq, Eq)]
pub enum FnInfo {
    Declared,
    Defined(String, HashSet<Arity>, HashSet<String>),
    Unknown,
}

fn match_arities(arities: &HashSet<Arity>, num_args: u8) -> bool {
    arities.iter().any(|arity| match arity {
        Arity::Fixed(n) => *n == num_args,
        Arity::Splat(n) => *n <= num_args,
    })
}

#[derive(Debug, PartialEq)]
pub struct Validator<'a> {
    pub locals: Vec<(String, &'a Span, FnInfo)>,
    pub prelude: imbl::HashMap<Key, Value>,
    pub input: &'static str,
    pub src: &'static str,
    pub ast: &'a Ast,
    pub span: &'a Span,
    pub errors: Vec<VErr<'a>>,
    pub fn_info: HashMap<*const Ast, FnInfo>,
    status: VStatus,
}

impl<'a> Validator<'a> {
    pub fn new(
        ast: &'a Ast,
        span: &'a Span,
        input: &'static str,
        src: &'static str,
        prelude: imbl::HashMap<Key, Value>,
    ) -> Validator<'a> {
        Validator {
            input,
            src,
            locals: vec![],
            prelude,
            ast,
            span,
            fn_info: std::collections::HashMap::new(),
            errors: vec![],
            status: VStatus {
                tail_position: false,
                in_loop: false,
                loop_arity: 0,
                last_term: false,
                has_placeholder: false,
                used_bindings: vec![],
            },
        }
    }

    fn bind(&mut self, name: String) {
        self.locals.push((name, self.span, FnInfo::Unknown));
    }

    fn declare_fn(&mut self, name: String) {
        self.locals.push((name, self.span, FnInfo::Declared));
    }

    fn define_fn(&mut self, name: String, info: FnInfo) {
        let i = self.locals.iter().position(|(n, ..)| *n == name).unwrap();
        let new_binding = (name, self.locals[i].1, info);
        self.locals[i] = new_binding;
    }

    fn resolved(&self, name: &'static str) -> bool {
        self.locals.iter().any(|(bound, ..)| name == bound.as_str())
            || self
                .prelude
                .iter()
                .any(|(bound, _)| Key::Keyword(name) == *bound)
    }

    fn bound(&self, name: &str) -> Option<&(String, &Span, FnInfo)> {
        match self.locals.iter().rev().find(|(bound, ..)| name == bound) {
            Some(binding) => Some(binding),
            None => None,
        }
    }

    fn err(&mut self, msg: String) {
        self.errors
            .push(VErr::new(msg, self.span, self.input, self.src))
    }

    fn use_name(&mut self, name: String) {
        self.status.used_bindings.push(name);
    }

    fn arity(&mut self) -> Arity {
        let Ast::MatchClause(pattern, ..) = self.ast else {
            unreachable!("internal Ludus error")
        };
        let (Ast::TuplePattern(members), _) = pattern.as_ref() else {
            unreachable!("internal Ludus error");
        };
        let last_member = members.last();
        match last_member {
            None => Arity::Fixed(0),
            Some((Ast::Splattern(..), _)) => Arity::Splat(members.len() as u8),
            Some(_) => Arity::Fixed(members.len() as u8),
        }
    }

    fn visit(&mut self, node: &'a Spanned<Ast>) {
        let (expr, span) = node;
        self.ast = expr;
        self.span = span;
        self.validate();
    }

    pub fn validate(&mut self) {
        use Ast::*;
        let root = self.ast;
        match root {
            Error => unreachable!(),
            Word(name) | Splat(name) => {
                if !self.resolved(name) {
                    self.err(format!("unbound name `{name}`"))
                } else {
                    self.use_name(name.to_string())
                }
            }
            Interpolated(parts) => {
                for part in parts {
                    if let (StringPart::Word(name), span) = part {
                        self.span = span;
                        if !self.resolved(name) {
                            self.err(format!("unbound name `{name}`"));
                        } else {
                            self.use_name(name.to_string());
                        }
                    }
                }
            }
            // validate each line
            // ensure it's not empty
            // pass through tail position validation
            // check if there are any declared but undefined functions
            // pop all the bindings off the local stack
            Block(block) => {
                if block.is_empty() {
                    self.err("blocks must have at least one expression".to_string());
                    return;
                }
                let to = self.locals.len();
                let tailpos = self.status.tail_position;
                for line in block.iter().take(block.len() - 1) {
                    self.status.tail_position = false;
                    self.visit(line);
                }

                self.status.tail_position = tailpos;
                self.visit(block.last().unwrap());

                let block_bindings = self.locals.split_off(to);

                for binding in block_bindings {
                    let (name, _, fn_info) = binding;
                    if matches!(fn_info, FnInfo::Declared) {
                        self.err(format!("fn `{name}` is declared but not defined"))
                    }
                }
            }
            // if in tail position, pass through tail position validation
            // no unbound names
            If(cond, then, r#else) => {
                let tailpos = self.status.tail_position;
                self.status.tail_position = false;

                self.visit(cond.as_ref());

                // pass through tailpos only to then/else
                self.status.tail_position = tailpos;
                self.visit(then.as_ref());
                self.visit(r#else.as_ref());
            }
            Tuple(members) => {
                if members.is_empty() {
                    return;
                }
                let tailpos = self.status.tail_position;
                self.status.tail_position = false;
                for member in members {
                    self.visit(member);
                }
                self.status.tail_position = tailpos;
            }
            // no more than one placeholder
            Arguments(args) => {
                if args.is_empty() {
                    return;
                }
                let tailpos = self.status.tail_position;
                self.status.tail_position = false;
                for arg in args {
                    self.visit(arg);
                }
                self.status.has_placeholder = false;
                self.status.tail_position = tailpos;
            }
            Placeholder => {
                if self.status.has_placeholder {
                    self.err(
                        "you may only use one placeholder when partially applying functions"
                            .to_string(),
                    );
                }
                self.status.has_placeholder = true;
            }
            List(list) => {
                if list.is_empty() {
                    return;
                }
                let tailpos = self.status.tail_position;
                self.status.tail_position = false;
                for member in list {
                    self.visit(member);
                }

                self.status.tail_position = tailpos;
            }
            KeywordPair(_, value) | StringPair(_, value) => self.visit(value.as_ref()),
            Dict(dict) => {
                if dict.is_empty() {
                    return;
                }
                let tailpos = self.status.tail_position;
                self.status.tail_position = false;
                for pair in dict {
                    self.visit(pair)
                }
                self.status.tail_position = tailpos;
            }

            // TODO!
            // check arity against fn info if first term is word and second term is args
            Synthetic(first, second, rest) => {
                match (&first.0, &second.0) {
                    (Ast::Word(_), Ast::Method(_, args)) => {
                        self.visit(first.as_ref());
                        self.visit(args);
                    }
                    (Ast::Keyword(_), Ast::Method(_, args)) => {
                        self.visit(args);
                    }
                    (Ast::And, Ast::Arguments(_)) | (Ast::Or, Ast::Arguments(_)) => {
                        self.visit(second.as_ref())
                    }
                    (Ast::Word(_), Ast::Keyword(_)) => self.visit(first.as_ref()),
                    (Ast::Keyword(_), Ast::Arguments(args)) => {
                        if args.len() != 1 {
                            self.err("called keywords may only take one argument".to_string())
                        }
                        self.visit(second.as_ref());
                    }
                    (Ast::Word(name), Ast::Arguments(args)) => {
                        self.visit(first.as_ref());
                        self.visit(second.as_ref());

                        //TODO: check arities of prelude fns, too
                        let fn_binding = self.bound(name);
                        if let Some((_, _, FnInfo::Defined(_, arities, _))) = fn_binding {
                            let num_args = args.len();
                            if !match_arities(arities, num_args as u8) {
                                self.err(format!("arity mismatch: no clause in function `{name}` with {num_args} argument(s)"))
                            }
                        }
                    }
                    _ => unreachable!(
                        "malformed synthetic root with\nfirst: {}\nsecond: {}",
                        first.0, second.0
                    ),
                }
                for term in rest {
                    self.visit(term);
                }
            }
            WhenClause(cond, body) => {
                let tailpos = self.status.tail_position;
                self.status.tail_position = false;
                self.visit(cond.as_ref());
                //pass through tail position for when bodies
                self.status.tail_position = tailpos;
                self.visit(body.as_ref());
            }
            When(clauses) => {
                for clause in clauses {
                    self.visit(clause);
                }
            }

            // binding forms
            // TODO: set up errors to include original binding
            LBox(name, boxed) => {
                if self.bound(name).is_some() {
                    self.err(format!("box name `{name}` is already bound"));
                } else {
                    self.bind(name.to_string());
                }
                self.visit(boxed.as_ref());
            }
            Let(lhs, rhs) => {
                self.visit(rhs.as_ref());
                self.visit(lhs.as_ref());
            }
            MatchClause(pattern, guard, body) => {
                let to = self.locals.len();

                self.visit(pattern.as_ref());

                if let Some(guard) = guard.as_ref() {
                    self.visit(guard);
                }

                self.visit(body.as_ref());

                self.locals.truncate(to);
            }
            Match(scrutinee, clauses) => {
                self.visit(scrutinee.as_ref());

                for clause in clauses {
                    self.visit(clause);
                }
            }
            Receive(clauses) => {
                for clause in clauses {
                    self.visit(clause);
                }
            }
            FnDeclaration(name) => {
                let tailpos = self.status.tail_position;
                self.status.tail_position = false;
                if self.bound(name).is_some() {
                    self.err(format!("fn name `{name}` is already bound"));
                    return;
                }
                self.declare_fn(name.to_string());
                self.status.tail_position = tailpos;
            }
            FnBody(..) => unreachable!(),
            Fn(name, body, ..) => {
                let mut is_declared = false;
                match self.bound(name) {
                    Some((_, _, FnInfo::Declared)) => is_declared = true,
                    None => (),
                    _ => {
                        self.err(format!("name `{name}` is already bound"));
                    }
                }

                // TODO: devise a placeholder binding for recursive functions
                if !is_declared {
                    self.declare_fn(name.to_string());
                }

                let from = self.status.used_bindings.len();
                let mut arities = HashSet::new();

                let (Ast::FnBody(clauses), _) = body.as_ref() else {
                    unreachable!()
                };

                for clause in clauses {
                    // we have to do this explicitly here because of arity checking
                    let (expr, span) = clause;
                    self.ast = expr;
                    self.span = span;
                    // add clause arity to arities
                    arities.insert(self.arity());
                    self.validate();
                }

                // collect info about what the function closes over
                let mut closed_over = HashSet::new();
                for binding in self.status.used_bindings.iter().skip(from) {
                    if self.bound(binding.as_str()).is_some() {
                        // println!("{name} closing over {binding}");
                        closed_over.insert(binding.clone());
                    }
                }

                let info = FnInfo::Defined(name.to_string(), arities, closed_over);

                let root_ptr: *const Ast = root;

                self.fn_info.insert(root_ptr, info.clone());

                self.define_fn(name.to_string(), info);
            }

            Panic(msg) => {
                let tailpos = self.status.tail_position;
                self.status.tail_position = false;
                self.visit(msg.as_ref());
                self.status.tail_position = tailpos;
            }
            // TODO: fix the tail call here?
            Do(terms) => {
                if terms.len() < 2 {
                    return self.err("do expressions must have at least two terms".to_string());
                }
                for term in terms.iter().take(terms.len() - 1) {
                    self.visit(term);
                }
                let last = terms.last().unwrap();
                self.visit(last);
                if matches!(last.0, Ast::Recur(_)) {
                    self.err("`recur` may not be used in `do` forms".to_string());
                }
            }
            Repeat(times, body) => {
                self.status.tail_position = false;
                self.visit(times.as_ref());
                self.visit(body.as_ref());
            }
            Loop(with, body) => {
                self.visit(with.as_ref());

                let Ast::Tuple(input) = &with.0 else {
                    unreachable!()
                };

                // dbg!(&input);

                let tailpos = self.status.tail_position;
                self.status.tail_position = true;
                let in_loop = self.status.in_loop;
                let outer_arity = self.status.loop_arity;
                self.status.in_loop = true;
                let loop_arity = input.len() as u8;
                self.status.loop_arity = loop_arity;

                for clause in body {
                    let (expr, span) = clause;
                    self.ast = expr;
                    self.span = span;
                    let arity = self.arity();
                    // dbg!(&arity);
                    match arity {
                        Arity::Fixed(clause_arity) => {
                            if clause_arity != loop_arity {
                                self.err(format!("mismatched arity: expected {loop_arity} arguments in `loop` clause; got {clause_arity}"))
                            }
                        }
                        Arity::Splat(clause_arity) => {
                            if clause_arity > loop_arity {
                                self.err(format!("mismathced arity: expected {loop_arity} arguments in `loop` clause; this clause takes {clause_arity} or more"))
                            }
                        }
                    };
                    self.validate();
                }

                self.status.tail_position = tailpos;
                self.status.in_loop = in_loop;
                self.status.loop_arity = outer_arity;
            }
            Recur(args) => {
                if !self.status.in_loop {
                    self.err("you may only use `recur` in a `loop` form".to_string());
                    return;
                }
                if !self.status.tail_position {
                    self.err("you may only use `recur` in tail position".to_string());
                }

                let num_args = args.len() as u8;
                let loop_arity = self.status.loop_arity;
                if num_args != loop_arity {
                    self.err(format!("loop arity mismatch: loop has arity of {loop_arity}; `recur` called with {num_args} arguments"))
                }

                self.status.tail_position = false;
                for arg in args {
                    self.visit(arg);
                }
            }
            WordPattern(name) => match self.bound(name) {
                Some((name, _span, _)) => {
                    self.err(format!("name `{name}` is already bound"));
                }
                None => {
                    self.bind(name.to_string());
                }
            },
            InterpolatedPattern(parts) => {
                for (part, span) in parts {
                    if let StringPart::Word(name) = part {
                        self.span = span;
                        match self.bound(name) {
                            Some(_) => self.err(format!("name `{name}` is already bound")),
                            None => self.bind(name.to_string()),
                        }
                    }
                }
            }
            AsPattern(name, r#type) => {
                match self.bound(name) {
                    Some((name, _span, _)) => {
                        self.err(format!("name `{name}` is already bound"));
                    }
                    None => {
                        self.bind(name.to_string());
                    }
                }
                let as_type = *r#type;
                match as_type {
                    "nil" | "bool" | "number" | "keyword" | "string" | "tuple" | "dict"
                    | "list" | "fn" | "box" => (),
                    _ => self.err(format!("unknown type `:{as_type}`")),
                }
            }
            Splattern(splatted) => {
                if !self.status.last_term {
                    self.err("splats in patterns must come last".to_string());
                }
                match splatted.as_ref() {
                    (PlaceholderPattern, _) => (),
                    (WordPattern(name), span) => match self.bound(name) {
                        Some(_) => {
                            self.span = span;
                            self.err(format!("name `{name}` is already bound"))
                        }
                        None => self.bind(name.to_string()),
                    },
                    _ => {
                        println!("internal Ludus error: unexpected splat pattern");
                        // dbg!(splatted);
                        unreachable!()
                    }
                }
            }
            TuplePattern(terms) | ListPattern(terms) | DictPattern(terms) => {
                if terms.is_empty() {
                    return;
                }
                for term in terms.iter().take(terms.len() - 1) {
                    self.visit(term);
                }

                self.status.last_term = true;
                let last = terms.last().unwrap();
                self.visit(last);
                self.status.last_term = false;
            }
            KeyPairPattern(_, patt) | StrPairPattern(_, patt) => self.visit(patt.as_ref()),
            // terminals can never be invalid
            Nil | Boolean(_) | Number(_) | Keyword(_) | String(_) | And | Or | Method(..) => (),
            // terminal patterns can never be invalid
            NilPattern | BooleanPattern(..) | NumberPattern(..) | StringPattern(..)
            | KeywordPattern(..) | PlaceholderPattern => (),
        };
        self.ast = root;
    }
}
