use crate::sexp::{SExp, SExp::*, SLeaf::*, util::*};

impl SExp {

    /// Evaluates the s-expression one step.
    ///
    /// **Integer operations**
    ///
    /// Addition, subtraction, multiplication and division
    /// are supported.
    /// ```rust
    /// use myslip::sexp::{SExp::*, SLeaf::*, util::*};
    ///
    /// assert_eq!(
    ///     scons(Add, scons(1, scons(1, Nil))).step(),
    ///     Ok(Atom(Int(2)))
    /// );
    ///
    /// assert_eq!(
    ///     scons(Sub, scons(1, scons(2, Nil))).step(),
    ///     Ok(Atom(Int(-1)))
    /// );
    ///
    /// assert_eq!(
    ///     scons(Mul, scons(2, scons(3, Nil))).step(),
    ///     Ok(Atom(Int(6)))
    /// );
    ///
    /// assert_eq!(
    ///     scons(Div, scons(6, scons(2, Nil))).step(),
    ///     Ok(Atom(Int(3)))
    /// );
    /// ```
    ///
    /// Division truncates the decimals.
    /// ```rust
    /// use myslip::sexp::{SExp::*, SLeaf::*, util::*};
    ///
    /// assert_eq!(
    ///     scons(Div, scons(5, scons(2, Nil))).step(),
    ///     Ok(Atom(Int(2)))
    /// );
    /// ```
    ///
    /// Also, addition and multiplication can take more than two arguments:
    /// (as of 2025-08-05 not allowed by the type system, might change)
    /// ```rust
    /// use myslip::sexp::{SExp::*, SLeaf::*, util::*};
    ///
    /// assert_eq!(
    ///     scons(Add, scons(1, scons(2, scons(3, Nil)))).step(),
    ///     Ok(Atom(Int(6)))
    /// );
    ///
    /// assert_eq!(
    ///     scons(Mul, scons(1, scons(2, scons(3, Nil)))).step(),
    ///     Ok(Atom(Int(6)))
    /// );
    /// ```
    ///
    /// Here's an example of a bit more complicated expression
    /// from wikipedias article on s-expressions.
    /// ```rust
    /// use myslip::sexp::{SExp::*, SLeaf::*, util::*};
    ///
    /// fn main() {
    ///     let exp = scons(
    ///         Mul,
    ///         scons(
    ///             2,
    ///             scons(
    ///                 scons(Add, scons(3, scons(4, Nil))),
    ///                 Nil
    ///             )
    ///         )
    ///     );
    ///
    ///     let exp = exp.step().unwrap();
    ///     assert_eq!(exp, scons(Mul, scons(2, scons(7, Nil))));
    ///
    ///     let exp = exp.step().unwrap();
    ///     assert_eq!(exp, Atom(Int(14)));
    /// }
    ///
    /// ```
    ///
    /// **Integer comparisons**
    ///
    /// ```rust
    /// use myslip::sexp::{SExp::*, SLeaf::*, util::*};
    ///
    /// assert_eq!(
    ///     scons(Lt, scons(1, scons(2, Nil))).step(),
    ///     Ok(Atom(True))
    /// );
    /// assert_eq!(
    ///     scons(Lt, scons(2, scons(2, Nil))).step(),
    ///     Ok(Atom(False))
    /// );
    ///
    /// assert_eq!(
    ///     scons(Gt, scons(2, scons(1, Nil))).step(),
    ///     Ok(Atom(True))
    /// );
    /// assert_eq!(
    ///     scons(Lt, scons(1, scons(1, Nil))).step(),
    ///     Ok(Atom(False))
    /// );
    ///
    /// assert_eq!(
    ///     scons(Le, scons(1, scons(2, Nil))).step(),
    ///     Ok(Atom(True)), "le 1"
    /// );
    /// assert_eq!(
    ///     scons(Le, scons(2, scons(2, Nil))).step(),
    ///     Ok(Atom(True)), "le 2"
    /// );
    /// assert_eq!(
    ///     scons(Le, scons(2, scons(1, Nil))).step(),
    ///     Ok(Atom(False)), "le 3"
    /// );
    ///
    /// assert_eq!(
    ///     scons(Ge, scons(2, scons(1, Nil))).step(),
    ///     Ok(Atom(True)), "ge 1"
    /// );
    /// assert_eq!(
    ///     scons(Ge, scons(1, scons(1, Nil))).step(),
    ///     Ok(Atom(True)), "ge 2"
    /// );
    /// assert_eq!(
    ///     scons(Ge, scons(1, scons(2, Nil))).step(),
    ///     Ok(Atom(False)), "ge 3"
    /// );
    ///
    /// assert_eq!(
    ///     scons(Eq, scons(1, scons(2, Nil))).step(),
    ///     Ok(Atom(False))
    /// );
    /// assert_eq!(
    ///     scons(Eq, scons(2, scons(2, Nil))).step(),
    ///     Ok(Atom(True))
    /// );
    ///
    /// assert_eq!(
    ///     scons(Neq, scons(1, scons(2, Nil))).step(),
    ///     Ok(Atom(True))
    /// );
    /// assert_eq!(
    ///     scons(Neq, scons(2, scons(2, Nil))).step(),
    ///     Ok(Atom(False))
    /// );
    /// ```
    ///
    /// **Boolean expressions**
    ///
    /// ```rust
    /// use myslip::sexp::{SExp::*, SLeaf::*, util::*};
    /// assert_eq!(
    ///     scons(And, scons(True, scons(True, Nil))).step(),
    ///     Ok(Atom(True))
    /// );
    /// assert_eq!(
    ///     scons(And, scons(False, scons(True, Nil))).step(),
    ///     Ok(Atom(False))
    /// );
    ///
    /// assert_eq!(
    ///     scons(Or, scons(False, scons(True, Nil))).step(),
    ///     Ok(Atom(True))
    /// );
    /// assert_eq!(
    ///     scons(Or, scons(False, scons(False, Nil))).step(),
    ///     Ok(Atom(False))
    /// );
    ///
    /// assert_eq!(
    ///     scons(Xor, scons(False, scons(True, Nil))).step(),
    ///     Ok(Atom(True))
    /// );
    /// assert_eq!(
    ///     scons(Xor, scons(False, scons(False, Nil))).step(),
    ///     Ok(Atom(False))
    /// );
    /// assert_eq!(
    ///     scons(Xor, scons(True, scons(True, Nil))).step(),
    ///     Ok(Atom(False))
    /// );
    ///
    /// assert_eq!(
    ///     scons(Not, scons(True, Nil)).step(),
    ///     Ok(Atom(False))
    /// );
    /// assert_eq!(
    ///     scons(Not, scons(False, Nil)).step(),
    ///     Ok(Atom(True))
    /// );
    /// ```
    ///
    /// **Quotes**
    ///
    /// If an s-expression should not be evaluated
    /// as a function, but it is instead to be treated
    /// as a list, `quote` can be used.
    /// With it as the operator, the rest of the list
    /// is evaluated to values, but they are not passed
    /// to the operator after that.
    ///
    /// ```rust
    /// use myslip::sexp::{SExp::*, SLeaf::*, util::*};
    /// assert_eq!(
    ///     scons(Quote, scons(1, scons(2, Nil))).step(),
    ///     Ok(scons(Quote, scons(1, scons(2, Nil))))
    /// );
    /// assert_eq!(
    ///     scons(Quote, scons(
    ///         scons(Sub, scons(2, scons(1, Nil))),
    ///     scons(2, Nil))).step(),
    ///     Ok(scons(Quote, scons(1, scons(2, Nil))))
    /// );
    /// ```
    ///
    /// **Vectors**
    ///
    /// The same as quotes functionally, but they require
    /// the elements to be of the same type.
    /// ```rust
    /// use myslip::sexp::{SExp::*, SLeaf::*, util::*};
    /// assert_eq!(
    ///     scons(Vector, scons(1, scons(2, Nil))).step(),
    ///     Ok(scons(Vector, scons(1, scons(2, Nil))))
    /// );
    /// assert_eq!(
    ///     scons(Vector, scons(
    ///         scons(Sub, scons(2, scons(1, Nil))),
    ///     scons(2, Nil))).step(),
    ///     Ok(scons(Vector, scons(1, scons(2, Nil))))
    /// );
    /// ```
    ///
    /// **Let-bindings**
    ///
    /// Basic operation:
    /// ```rust
    /// use myslip::sexp::{SExp::*, SLeaf::*, util::*};
    ///
    /// assert_eq!(
    ///     scons(
    ///         scons(Let, scons(var("x"), scons(5, Nil))), scons(
    ///             scons(Add, scons(var("x"), scons(1, Nil))), Nil
    ///         )
    ///     ).step(),
    ///     Ok(scons(Add, scons(5, scons(1, Nil))))
    /// );
    /// assert_eq!(
    ///     scons(
    ///         scons(Let, scons(var("y"), scons(4, Nil))),
    ///         scons(
    ///             scons(Let, scons(var("x"), scons(5, Nil))),
    ///             scons(scons(Add, scons(var("x"), scons(var("y"), Nil))), Nil)
    ///         )
    ///     ).step(),
    ///     Ok(scons(
    ///         scons(Let, scons(var("x"), scons(5, Nil))), scons(
    ///             scons(Add, scons(var("x"), scons(4, Nil))), Nil
    ///         )
    ///     ))
    /// );
    /// ```
    ///
    /// Shadowing:
    /// ```rust
    /// use myslip::sexp::{SExp::*, SLeaf::*, util::*};
    ///
    /// assert_eq!(
    ///     scons(
    ///         scons(Let, scons(var("x"), scons(4, Nil))),
    ///         scons(
    ///             scons(Let, scons(var("x"), scons(5, Nil))),
    ///             scons(scons(Add, scons(var("x"), scons(4, Nil))), Nil)
    ///         )
    ///     ).step(),
    ///     Ok(scons(
    ///         scons(Let, scons(var("x"), scons(5, Nil))), scons(
    ///             scons(Add, scons(var("x"), scons(4, Nil))), Nil
    ///         )
    ///     ))
    /// );
    /// ```
    /// 
    pub fn step(self) -> Result<Self, String> {
        match self {

            // List processing

            //     op not a value
            // -----------------------
            // (op x) -> (op.step() x)
            SCons(op, l) if !(*op).is_value() => Ok(scons(op.step()?, l)),


            // let binds
            SCons(op, l) if op.clone().check_let().is_some() => match (*op).check_let() {
                Some((varname, val)) => Ok(match *l {
                    SCons(a, b) if *b == Atom(Nil) => *a,
                    t => t,
                }.subst(&varname, &val)),
                None => panic!("unreachable as per match guard arm"),
            },


            // op value and a1 .. an values, and b0, b1 .. bn not values
            // ---------------------------------------------------------
            //   (op a1 ... an b) -> (op a1 ... an b0.step() b1 .. bn)
            SCons(op, l) if !(*l).consists_of_values() => {
                fn inner(s: SExp) -> Result<SExp, String> {
                    match s {
                        SCons(a, b) if (*a).is_value() => Ok(scons(a, inner(*b)?)),
                        SCons(a, b) => Ok(scons(a.step()?, b)),
                        x => x.step()
                    }
                }
                Ok(scons(op, inner(*l)?))
            },


            // Arithmetic


            //      t1, ..., tn integers
            // ------------------------------
            // (+ t1 ... tn) -> t1 + ... + tn
            SCons(op, l) if *op == Atom(Add) => l.into_vec()?
                .iter()
                .fold(
                    Ok(0),
                    |acc, el| {
                        match el {
                            Int(x) => acc.map(|v| x+v),
                            _ => Err(
                                "'+' should only be given integers".to_string()
                                )
                        }
                    }
                ).map(|x| Atom(Int(x))),


            //      t1, ..., tn integers
            // ------------------------------
            // (* t1 ... tn) -> t1 * ... * tn
            SCons(op, l) if *op == Atom(Mul) => l.into_vec()?
                .iter()
                .fold(
                    Ok(1),
                    |acc, el| {
                        match el {
                            Int(x) => acc.map(|v| x*v),
                            _ => Err(
                                format!("'*' should only be given integers, found {:?}", el)
                                )
                        }
                    }
                ).map(|x| Atom(Int(x))),


            //    t1,t2 integers
            // --------------------
            // (- t1 t2) -> t1 - t2
            SCons(op, l) if *op == Atom(Sub) => {
                let ls = l.into_vec()?;
                if ls.len() == 2 {
                    match (ls[0].clone(), ls[1].clone()) {
                        (Int(a), Int(b)) => Ok(Atom(Int(a - b))),
                        _ => Err("'-' should be only given integers".to_string())
                    }
                } else {
                    Err(format!("'-' should be given 2 arguments, found {}", ls.len()))
                }
            },


            //    t1,t2 integers
            // --------------------
            // (/ t1 t2) -> t1 / t2
            SCons(op, l) if *op == Atom(Div) => {
                let ls = l.into_vec()?;
                if ls.len() == 2 {
                    match (ls[0].clone(), ls[1].clone()) {
                        (_, Int(0)) => Err("division by zero".to_string()),
                        (Int(a), Int(b)) => Ok(Atom(Int(a / b))),
                        _ => Err("'/' should be only given integers".to_string())
                    }
                } else {
                    Err(format!("'/' should be given 2 arguments, found {}", ls.len()))
                }
            },


            //    t1,t2 booleans
            // -----------------------
            // (and t1 t2) -> t1 && t2
            SCons(op, l) if *op == Atom(And) => {
                let ls = l.into_vec()?;
                if ls.len() == 2 {
                    match (ls[0].clone(), ls[1].clone()) {
                        (True, True) => Ok(Atom(True)),
                        (True | False, True | False) => Ok(Atom(False)),
                        _ => Err("'and' should be only given booleans".to_string())
                    }
                } else {
                    Err(format!("'and' should be given 2 arguments, found {}", ls.len()))
                }
            },

            //    t1,t2 booleans
            // -----------------------
            // (or t1 t2) -> t1 || t2
            SCons(op, l) if *op == Atom(Or) => {
                let ls = l.into_vec()?;
                if ls.len() == 2 {
                    match (ls[0].clone(), ls[1].clone()) {
                        (False, False) => Ok(Atom(False)),
                        (True | False, True | False) => Ok(Atom(True)),
                        _ => Err("'or' should be only given booleans".to_string())
                    }
                } else {
                    Err(format!("'or' should be given 2 arguments, found {}", ls.len()))
                }
            },

            // t1,t2 booleans
            // --------------
            // (xor t1 t2) -> t1 ^ t2
            SCons(op, l) if *op == Atom(Xor) => {
                let ls = l.into_vec()?;
                let t1 = ls.get(0).ok_or("wrong list length".to_string())?;
                let t2 = ls.get(1).ok_or("wrong list length".to_string())?;
                match (t1, t2) {
                    (True, False) => Ok(Atom(True)),
                    (False, True) => Ok(Atom(True)),
                    (True | False, True | False) => Ok(Atom(False)),
                    _ => Err("invalid args".to_string()),
                }
            },

            // Not
            SCons(op, l) if *op == Atom(Not) => {
                let ls = l.into_vec()?;
                let t1 = ls.get(0).ok_or("wrong list length".to_string())?;
                match t1 {
                    True => Ok(Atom(False)),
                    False => Ok(Atom(True)),
                    _ => Err("invalid args".to_string()),
                }
            },

            // Lt
            SCons(op, l) if *op == Atom(Lt) => {
                let ls = l.into_vec()?;
                let t1 = ls.get(0).ok_or("wrong list length".to_string())?;
                let t2 = ls.get(1).ok_or("wrong list length".to_string())?;
                match (t1, t2) {
                    (Int(a), Int(b)) => Ok((a < b).into()),
                    _ => Err("invalid args".to_string()),
                }
            },

            // Gt
            SCons(op, l) if *op == Atom(Gt) => {
                let ls = l.into_vec()?;
                let t1 = ls.get(0).ok_or("wrong list length".to_string())?;
                let t2 = ls.get(1).ok_or("wrong list length".to_string())?;
                match (t1, t2) {
                    (Int(a), Int(b)) => Ok((a > b).into()),
                    _ => Err("invalid args".to_string()),
                }
            },

            // Le
            SCons(op, l) if *op == Atom(Le) => {
                let ls = l.into_vec()?;
                let t1 = ls.get(0).ok_or("wrong list length".to_string())?;
                let t2 = ls.get(1).ok_or("wrong list length".to_string())?;
                match (t1, t2) {
                    (Int(a), Int(b)) => Ok((a <= b).into()),
                    _ => Err("invalid args".to_string()),
                }
            },

            // Ge
            SCons(op, l) if *op == Atom(Ge) => {
                let ls = l.into_vec()?;
                let t1 = ls.get(0).ok_or("wrong list length".to_string())?;
                let t2 = ls.get(1).ok_or("wrong list length".to_string())?;
                match (t1, t2) {
                    (Int(a), Int(b)) => Ok((a >= b).into()),
                    _ => Err("invalid args".to_string()),
                }
            },

            // Eq
            SCons(op, l) if *op == Atom(Eq) => {
                let ls = l.into_vec()?;
                let t1 = ls.get(0).ok_or("wrong list length".to_string())?;
                let t2 = ls.get(1).ok_or("wrong list length".to_string())?;
                match (t1, t2) {
                    (Int(a), Int(b)) => Ok((a == b).into()),
                    _ => Err("invalid args".to_string()),
                }
            },

            // Neq
            SCons(op, l) if *op == Atom(Neq) => {
                let ls = l.into_vec()?;
                let t1 = ls.get(0).ok_or("wrong list length".to_string())?;
                let t2 = ls.get(1).ok_or("wrong list length".to_string())?;
                match (t1, t2) {
                    (Int(a), Int(b)) => Ok((a != b).into()),
                    _ => Err("invalid args".to_string()),
                }
            },

            // t is value
            // ----------
            //   t -> t
            t if t.is_value() => Ok(t),

            t => Err(format!("unimplemented: {:?}.step()", t)),
        }
    }


    pub fn multistep(self) -> Result<Self, String> {
        match self.clone().step()? {
            x if x == self => Ok(self),
            x => x.multistep()
        }
    }
}