1 files changed, 88 insertions, 0 deletions
diff --git a/src/sexp/case.rs b/src/sexp/case.rs
new file mode 100644
index 0000000..71f5007
--- /dev/null
+++ b/src/sexp/case.rs
@@ -0,0 +1,88 @@
+
+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
+	}
+    }
+}