//! A `macro_rules!` expander.
//!
//! The alternative was translating each `macro_rules!` into a Nim `template`,
//! which is the shape-level correspondence: 36% of the 1,833 definitions in a
//! 400-crate sample are a single rule with no repetition, which is exactly a
//! template, and another 40% map to a Nim `macro` over `varargs`.
//!
//! That correspondence is real but it does not survive contact with this
//! project's approach. A Nim template body is *untyped*: it is substituted and
//! only then type-checked. Our lowering is type-directed throughout — it needs
//! a type to choose `div` over `/`, to size a `cast`, to pick an integer
//! literal's width. Translating a macro body would mean lowering Rust with no
//! type information, which is precisely the guessing the project refuses.
//!
//! Expanding at the call site does not have that problem: the expansion is
//! ordinary Rust in a context where types are known, so it lowers like any
//! other code. Same applicability, faithful output.
//!
//! Implemented here: a single rule, no repetition, no `:tt`. That is the 36%.

use proc_macro2::{Delimiter, Group, Ident, TokenStream, TokenTree};
use std::collections::HashMap;

/// One element of a matcher: a captured fragment, or a token to match exactly.
#[derive(Debug, Clone)]
enum Pat {
    Frag(String),
    Tok(String),
    /// A delimited group, matched recursively.
    Group(Delimiter, Vec<Pat>),
}

#[derive(Debug, Clone)]
pub struct MacroDef {
    pattern: Vec<Pat>,
    body: TokenStream,
}

/// Parse `macro_rules!`'s body: `( $matcher ) => { $transcriber };`.
pub fn parse(tokens: TokenStream) -> Result<MacroDef, String> {
    let t: Vec<TokenTree> = tokens.into_iter().collect();
    // matcher group, `=`, `>`, transcriber group, optional `;`
    let (matcher, rest) = match t.split_first() {
        Some((TokenTree::Group(g), rest)) => (g.clone(), rest),
        _ => return Err("expected a matcher group".into()),
    };
    let arrow: String = rest.iter().take(2).map(|t| t.to_string()).collect();
    if arrow != "=>" {
        return Err("expected `=>`".into());
    }
    let body = match rest.get(2) {
        Some(TokenTree::Group(g)) => g.stream(),
        _ => return Err("expected a transcriber group".into()),
    };
    if rest.len() > 4 || (rest.len() == 4 && rest[3].to_string() != ";") {
        return Err("more than one rule is not implemented yet".into());
    }
    Ok(MacroDef { pattern: parse_pattern(matcher.stream())?, body })
}

fn parse_pattern(ts: TokenStream) -> Result<Vec<Pat>, String> {
    let mut out = Vec::new();
    let mut it = ts.into_iter().peekable();
    while let Some(t) = it.next() {
        match t {
            TokenTree::Punct(p) if p.as_char() == '$' => {
                match it.next() {
                    Some(TokenTree::Ident(name)) => {
                        // `$name:fragment`
                        match it.next() {
                            Some(TokenTree::Punct(c)) if c.as_char() == ':' => {}
                            _ => return Err("expected `:` after a fragment name".into()),
                        }
                        let kind = match it.next() {
                            Some(TokenTree::Ident(k)) => k.to_string(),
                            _ => return Err("expected a fragment specifier".into()),
                        };
                        if kind == "tt" {
                            return Err(
                                "`:tt` makes a macro a token-tree interpreter, which \
                                 has no mechanical translation"
                                    .into(),
                            );
                        }
                        out.push(Pat::Frag(name.to_string()));
                    }
                    Some(TokenTree::Group(_)) => {
                        return Err(
                            "`$(..)` repetition is not implemented yet; it maps to \
                             `varargs` in a Nim macro"
                                .into(),
                        )
                    }
                    _ => return Err("unexpected token after `$`".into()),
                }
            }
            TokenTree::Group(g) => {
                out.push(Pat::Group(g.delimiter(), parse_pattern(g.stream())?))
            }
            other => out.push(Pat::Tok(other.to_string())),
        }
    }
    Ok(out)
}

impl MacroDef {
    /// Match an invocation's tokens and substitute them into the body.
    pub fn expand(&self, input: TokenStream) -> Result<TokenStream, String> {
        let mut binds = HashMap::new();
        let toks: Vec<TokenTree> = input.into_iter().collect();
        let used = match_seq(&self.pattern, &toks, &mut binds)?;
        if used != toks.len() {
            return Err("the invocation has tokens the matcher does not consume".into());
        }
        Ok(substitute(self.body.clone(), &binds))
    }
}

/// Match `pats` against the front of `toks`, returning how many were consumed.
fn match_seq(
    pats: &[Pat],
    toks: &[TokenTree],
    binds: &mut HashMap<String, TokenStream>,
) -> Result<usize, String> {
    let mut i = 0;
    for (k, p) in pats.iter().enumerate() {
        match p {
            Pat::Tok(s) => {
                let t = toks.get(i).ok_or("the invocation ends before the matcher does")?;
                if t.to_string() != *s {
                    return Err(format!("expected `{s}`, found `{t}`"));
                }
                i += 1;
            }
            Pat::Group(d, inner) => {
                let Some(TokenTree::Group(g)) = toks.get(i) else {
                    return Err("expected a delimited group".into());
                };
                if g.delimiter() != *d {
                    return Err("mismatched delimiter".into());
                }
                let sub: Vec<TokenTree> = g.stream().into_iter().collect();
                let n = match_seq(inner, &sub, binds)?;
                if n != sub.len() {
                    return Err("group has tokens the matcher does not consume".into());
                }
                i += 1;
            }
            Pat::Frag(name) => {
                // A fragment runs to the next literal token in the matcher, or
                // to the end. That is what makes `$a:expr, $b:expr` split on
                // the comma rather than swallowing it.
                let stop = pats[k + 1..].iter().find_map(|p| match p {
                    Pat::Tok(s) => Some(s.clone()),
                    _ => None,
                });
                let start = i;
                let mut depth = 0i32;
                while i < toks.len() {
                    let s = toks[i].to_string();
                    if let Some(stop) = &stop {
                        if depth == 0 && s == *stop {
                            break;
                        }
                    }
                    match &toks[i] {
                        TokenTree::Punct(p) if p.as_char() == '<' => depth += 1,
                        TokenTree::Punct(p) if p.as_char() == '>' => depth -= 1,
                        _ => {}
                    }
                    i += 1;
                }
                if i == start {
                    return Err(format!("nothing matched fragment `${name}`"));
                }
                binds.insert(
                    name.clone(),
                    toks[start..i].iter().cloned().collect::<TokenStream>(),
                );
            }
        }
    }
    Ok(i)
}

/// Replace every `$name` in the body with what it captured.
fn substitute(ts: TokenStream, binds: &HashMap<String, TokenStream>) -> TokenStream {
    let mut out = Vec::new();
    let mut it = ts.into_iter().peekable();
    while let Some(t) = it.next() {
        match t {
            TokenTree::Punct(p) if p.as_char() == '$' => {
                match it.peek() {
                    Some(TokenTree::Ident(name)) => {
                        let n = name.to_string();
                        it.next();
                        match binds.get(&n) {
                            // Parenthesised so that a captured expression keeps
                            // its own precedence, as Rust's `expr` fragments do.
                            Some(v) => out.push(TokenTree::Group(Group::new(
                                Delimiter::Parenthesis,
                                v.clone(),
                            ))),
                            None => {
                                out.push(TokenTree::Punct(p));
                                out.push(TokenTree::Ident(Ident::new(
                                    &n,
                                    proc_macro2::Span::call_site(),
                                )));
                            }
                        }
                    }
                    _ => out.push(TokenTree::Punct(p)),
                }
            }
            TokenTree::Group(g) => {
                let inner = substitute(g.stream(), binds);
                out.push(TokenTree::Group(Group::new(g.delimiter(), inner)));
            }
            other => out.push(other),
        }
    }
    out.into_iter().collect()
}