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

impl SExp {
    /**
     * Matches this expression against the given pattern,
     * that may contain RestPats and variables.
     * upon successful match, variable bindings are returned.
     *
     * Two equal values match:
     * ```rust
     * use myslip::sexp::{SExp::*, SLeaf::*, util::*};
     * assert_eq!(scons(1, Nil).matches_pat(&scons(1, Nil)), Some(vec![]));
     * ```
     * A variable (wildcard) pattern matches the whole expression:
     * ```rust
     * use myslip::sexp::{SExp::*, SLeaf::*, util::*};
     * 
     * assert_eq!(
     *     scons(1, scons(scons(2, scons(3, Nil)), Nil))
     *         .matches_pat(&var("x")),
     *     Some(vec![(
     *         "x".to_string(),
     *         scons(1, scons(scons(2, scons(3, Nil)), Nil))
     *     )])
     * );
     * ```
     * If a variable has a similar place in structure, it matches
     * the corresponding part:
     * ```rust
     * use myslip::sexp::{SExp::*, SLeaf::*, util::*};
     * 
     * assert_eq!(
     *     scons(1, scons(scons(2, scons(3, Nil)), Nil))
     *         .matches_pat(&scons(var("x"), scons(var("y"), Nil))),
     *     Some(vec![
     *         ("x".to_string(), Atom(Int(1))),
     *         ("y".to_string(), scons(2, scons(3, Nil)))
     *     ])
     * );
     * ```
     * Rest patterns:
     * ```rust
     * use myslip::sexp::{SExp::*, SLeaf::*, util::*};
     * 
     * assert_eq!(
     *     scons(1, scons(2, scons(3, Nil)))
     *         .matches_pat(&scons(var("x"), scons(RestPat("y".to_string()), Nil))),
     *     Some(vec![
     *         ("x".to_string(), Atom(Int(1))),
     *         ("y".to_string(), scons(2, scons(3, Nil)))
     *     ])
     * );
     * ```
     */
    pub fn matches_pat(&self, pat: &SExp) -> Option<Vec<(String, SExp)>> {
	match (self, pat) {
	    
	    (a, b) if a == b => Some(vec![]),

	    (a, Atom(Var(name))) => Some(vec![(name.clone(), a.clone())]),

	    (SCons(a1, a2), SCons(b1, b2)) => {
		let lefthand = a1.matches_pat(b1);
		let checkres = (*b2).check_res_pat();
		let righthand = match checkres {
		    Some(name) => Some(vec![(name, *a2.clone())]),
		    None => a2.matches_pat(b2),
		};
		lefthand.zip(righthand)
		    .map(|vs| vs.0.into_iter().chain(vs.1).collect())
	    },

	    _ => todo!(),

	}
    }

    fn check_res_pat(&self) -> Option<String> {
	match self {
	    SCons(a, b) => match (*a.clone(), *b.clone()) {
		(Atom(RestPat(s)), Atom(Nil)) => Some(s),
		_ => None
	    },
	    _ => None
	}
    }
}