use std::{
    convert::TryFrom,
    collections::HashMap,
};

use crate::common::{
    stamp::stamp,
    span::{Span, Spanned},
};

use crate::compiler::{
    ast::{AST, ASTPattern, ArgPattern},
    syntax::Syntax
};

// TODO: immutably capture external values used by macro
// TODO: add context for macro application
// NOTE: add spans?

/// When a macro is expanded, `AST` slices captured by the macro Argument Pattern
/// are spliced into the macro body.
/// A `Binding` relates a name (within an Argument CSTPattern),
/// to an `AST` slice.
type Bindings = HashMap<String, Spanned<AST>>;

/// A rule has an Argument Pattern and an `AST`.
/// When a form matches the `ArgPattern`,
/// a set of bindings are produced,
/// which are then spliced into the Rule's `AST`
/// to make a new `AST`.
/// This is done in a hygenic manner.
#[derive(Debug, Clone)]
pub struct Rule {
    pub arg_pat: Spanned<ArgPattern>,
    pub tree: Spanned<AST>,
}

impl Rule {
    /// Builds a new rule, making sure the rule's signature is valid.
    pub fn new(
        arg_pat: Spanned<ArgPattern>,
        tree: Spanned<AST>,
    ) -> Result<Rule, Syntax> {
        if Rule::keywords(&arg_pat).len() == 0 {
            return Err(Syntax::error(
                "Syntactic macro must have at least one pseudokeyword",
                &arg_pat.span,
            ));
        }
        Ok(Rule { arg_pat, tree })
    }

    /// Returns all keywords, as strings, used by the macro, in order of usage.
    /// Does not filter for duplicates.
    pub fn keywords(arg_pat: &Spanned<ArgPattern>) -> Vec<String> {
        match &arg_pat.item {
            ArgPattern::Group(pats) => {
                let mut keywords = vec![];
                for pat in pats { keywords.append(&mut Rule::keywords(&pat)) }
                keywords
            },
            ArgPattern::Keyword(name) => vec![name.clone()],
            _ => vec![],
        }
    }

    /// Merges two maps of bindings.
    /// If there is a collision, i.e. a name bound in both bindings,
    /// An error highlighting the duplicate binding is returned.
    pub fn merge_safe(base: &mut Bindings, new: Bindings, def: Span) -> Result<(), Syntax> {
        let collision = Syntax::error(
            "Variable has already been declared in syntactic macro argument pattern", &def
        );

        for (n, t) in new {
            if base.contains_key(&n) { return Err(collision); }
            else                     { base.insert(n, t);     }
        }

        Ok(())
    }

    /// Traverses a form, creating bindings for subsequent transformation.
    /// Returns `None` if the form does not match the argument pattern.
    /// `Some(Ok(_))` if it matches successfully,
    /// and `Some(Err(_))` if it matches but something is incorrect.
    /// **You must check that the passed `&mut reversed_form` is empty
    /// to gaurantee the match occured in full**
    /// Note that this function takes the form unwrapped and in reverse -
    /// This is to make processing the bindings more efficient,
    /// As this function works with the head of the form.
    pub fn bind(arg_pat: &Spanned<ArgPattern>, mut reversed_form: &mut Vec<Spanned<AST>>)
    -> Option<Result<Bindings, Syntax>> {
        match &arg_pat.item {
            // TODO: right now, if a macro is invoked from another macro,
            // passerine won't recognize it,
            // because the pseudokeywords are hygenically replaced.
            // this should return true if a substituted pseudokeword
            // matches as well.
            // substitution scheme could be: `#name#tag`
            // and if name matches whole symbol matches.
            ArgPattern::Keyword(expected) => match reversed_form.pop()?.item {
                AST::Symbol(name) if &Rule::remove_tag(&name) == expected => {
                    Some(Ok(HashMap::new()))
                },
                _ => None,
            },
            ArgPattern::Symbol(symbol) => Some(Ok(
                vec![(symbol.clone(), reversed_form.pop()?)]
                    .into_iter().collect()
            )),
            ArgPattern::Group(pats) => {
                let mut bindings = HashMap::new();
                for pat in pats {
                    let span = pat.span.clone();
                    let new = match Rule::bind(&pat, &mut reversed_form)? {
                        Ok(matched) => matched,
                        mismatch @ Err(_) => return Some(mismatch),
                    };
                    if let Err(collision) = Rule::merge_safe(&mut bindings, new, span) {
                        return Some(Err(collision));
                    }
                }
                Some(Ok(bindings))
            },
        }
    }

    /// Turns a tagged random identifier, like
    /// `<base>#XXXXXXXX` back into `<base>`.
    /// If the identifier is not tagged, this function just
    /// returns `<base>`.
    pub fn remove_tag(base: &str) -> String {
        base.split("#").collect::<Vec<&str>>()[0].to_string()
    }

    /// Turns a base identifier into a random identifier
    /// of the format `<base>#XXXXXXXX`,
    /// Gauranteed not to exist in bindings.
    pub fn unique_tag(base: String, bindings: &Bindings) -> String {
        let mut tries = 0;
        for _ in 0..1024 {
            let stamp = stamp(tries);
            // for example, `foo` may become `foo#d56aea12`
            // this should not be constructible as a symbol.
            let modified = format!("{}#{}", base, stamp);
            if !bindings.contains_key(&modified) {
                // println!("{}", modified);
                return modified;
            }
            tries += 1;
        }
        panic!("Generated 1024 new unique identifiers for macro expansion, but all were already in use!");
    }

    /// Resolves a symbol.
    /// If the symbol has been bound, i.e. is defined in the Argument CSTPattern,
    /// we simply splice that in.
    /// If not, we hygenically replace it with a unique variable.
    pub fn resolve_symbol(name: String, span: Span, bindings: &mut Bindings) -> Spanned<AST> {
        if let Some(bound_tree) = bindings.get(&name) {
            bound_tree.clone()
        } else {
            let unique = Rule::unique_tag(name.clone(), bindings);
            let spanned = Spanned::new(AST::Symbol(unique.clone()), span.clone());
            bindings.insert(name, spanned);
            Spanned::new(AST::Symbol(unique), span)
        }
    }

    // TODO: move expansions to ast?

    /// Expands the bindings in a pattern.
    pub fn expand_pattern(
        pattern: Spanned<ASTPattern>,
        bindings: &mut Bindings,
    ) -> Result<Spanned<ASTPattern>, Syntax> {
        Ok(
            match pattern.item {
                ASTPattern::Symbol(name) => {
                    let span = pattern.span.clone();

                    Rule::resolve_symbol(name, pattern.span, bindings)
                    .map(ASTPattern::try_from)
                    .map_err(|s| Syntax::error(&s, &span))?
                },
                ASTPattern::Data(_) => pattern,
                // TODO: treat name as symbol?
                ASTPattern::Label(name, pattern) => {
                    let span = pattern.span.clone();
                    Spanned::new(
                        ASTPattern::label(name, Rule::expand_pattern(*pattern, bindings)?), span,
                    )
                },
                ASTPattern::Chain(chain) => {
                    let span = Spanned::build(&chain);
                    let expanded = chain.into_iter()
                        .map(|b| Rule::expand_pattern(b, bindings))
                        .collect::<Result<Vec<_>, _>>()?;
                    Spanned::new(ASTPattern::Chain(expanded), span)
                },
                ASTPattern::Tuple(tuple) => {
                    let span = Spanned::build(&tuple);
                    let expanded = tuple.into_iter()
                        .map(|b| Rule::expand_pattern(b, bindings))
                        .collect::<Result<Vec<_>, _>>()?;
                    Spanned::new(ASTPattern::Tuple(expanded), span)
                }
            }
        )
    }

    /// ~Macros inside of macros is a bit too meta for me to think about atm.~
    /// No longer!
    /// A macro inside a macro is a macro completely local to that macro.
    /// The argument patterns inside a macro can be extended.
    pub fn expand_arg_pat(
        arg_pat: Spanned<ArgPattern>,
        bindings: &mut Bindings,
    ) -> Result<Spanned<ArgPattern>, Syntax> {
        Ok(
            match arg_pat.item {
                ArgPattern::Keyword(_) => arg_pat,
                ArgPattern::Symbol(name) => {
                    let span = arg_pat.span.clone();

                    Rule::resolve_symbol(name, arg_pat.span, bindings)
                    .map(ArgPattern::try_from)
                    .map_err(|s| Syntax::error(&s, &span))?
                },
                ArgPattern::Group(sub_pat) => {
                    let span = Spanned::build(&sub_pat);
                    let expanded = sub_pat.into_iter()
                        .map(|b| Rule::expand_arg_pat(b, bindings))
                        .collect::<Result<Vec<_>, _>>()?;
                    Spanned::new(ArgPattern::Group(expanded), span)
                },
            }
        )
    }

    // TODO: break expand out into functions

    /// Takes a macro's tree and a set of bindings and produces a new hygenic tree.
    pub fn expand(tree: Spanned<AST>, mut bindings: &mut Bindings)
    -> Result<Spanned<AST>, Syntax> {
        // TODO: should macros evaluate arguments as thunks before insertions?
        // TODO: allow macros to reference external definitions
        let item: AST = match tree.item {
            // looks up symbol name in table of bindings
            // if it's found, it's replaced -
            // if it's not found, it's added to the table of bindings,
            // and replaced with a random symbol that does not collide with any other bindings
            // so that the next time the symbol is located,
            // it's consistently replaced, hygenically.
            AST::Symbol(name) => return Ok(Rule::resolve_symbol(name, tree.span.clone(), &mut bindings)),
            AST::Data(_) => return Ok(tree),

            // Apply the transformation to each form
            AST::Block(forms) => AST::Block(
                forms.into_iter()
                    .map(|f| Rule::expand(f, bindings))
                    .collect::<Result<Vec<_>, _>>()?
            ),

            // Apply the transformation to each item in the form
            AST::Form(branches) => AST::Form(
                branches.into_iter()
                    .map(|b| Rule::expand(b, bindings))
                    .collect::<Result<Vec<_>, _>>()?
            ),

            AST::Group(expression) => AST::group(Rule::expand(*expression, bindings)?),

            // Appy the transformation to the left and right sides of the composition
            AST::Composition { argument, function } => {
                let a = Rule::expand(*argument, bindings)?;
                let f = Rule::expand(*function, bindings)?;
                AST::composition(a, f)
            },

            // replace the variables in (argument) patterns
            AST::CSTPattern(pattern) => {
                let spanned = Spanned::new(pattern, tree.span.clone());
                AST::CSTPattern(Rule::expand_pattern(spanned, bindings)?.item)
            },
            AST::ArgPattern(arg_pat) => {
                let spanned = Spanned::new(arg_pat, tree.span.clone());
                AST::ArgPattern(Rule::expand_arg_pat(spanned, bindings)?.item)
            },

            // replace the variables in the patterns and the expression
            AST::Assign { pattern, expression } => {
                let p = Rule::expand_pattern(*pattern, bindings)?;
                let e = Rule::expand(*expression, bindings)?;
                AST::assign(p, e)
            },
            AST::Lambda { pattern, expression } => {
                let p = Rule::expand_pattern(*pattern, bindings)?;
                let e = Rule::expand(*expression, bindings)?;
                AST::lambda(p, e)
            },

            // TODO: Should labels be bindable in macros?
            AST::Label(kind, expression) => AST::Label(
                kind, Box::new(Rule::expand(*expression, bindings)?)
            ),

            AST::Tuple(tuple) => AST::Tuple(
                tuple.into_iter()
                    .map(|b| Rule::expand(b, bindings))
                    .collect::<Result<Vec<_>, _>>()?
            ),

            // a macro inside a macro. not sure how this should work yet
            AST::Syntax { arg_pat, expression } => {
                let ap = Rule::expand_arg_pat(*arg_pat, bindings)?;
                let e = Rule::expand(*expression, bindings)?;
                AST::syntax(ap, e);
                return Err(Syntax::error(
                    "Nested macros are not allowed",
                    &tree.span,
                ))?;
            },

            AST::FFI { name, expression } => AST::ffi(
                &name,
                Rule::expand(*expression, bindings)?
            ),
        };

        return Ok(Spanned::new(item, tree.span));
    }
}