refactor: Added helper matches_pat for pattern matching

5 files changed, 100 insertions, 0 deletions

diff --git a/src/parse/parsetree.rs b/src/parse/parsetree.rs
index 46e636c..7f9d9dc 100644
--- a/src/parse/parsetree.rs
+++ b/src/parse/parsetree.rs
@@ -117,9 +117,12 @@ fn tokens_to_ast_inner(
 	    Some(Sym(s)) if s == "print"  => Ok(Atom(Print)),
 	    Some(Sym(s)) if s == "let"    => Ok(Atom(Let)),
 	    Some(Sym(s)) if s == "fn"     => Ok(Atom(Fun)),
+	    Some(Sym(s)) if s == "case"   => Ok(Atom(Case)),
 	    Some(Sym(s)) if s == "->"     => Ok(Atom(Arr)),
 	    Some(Sym(s)) if s == "int"    => Ok(Atom(Ty(Integer))),
 	    Some(Sym(s)) if s == "bool"   => Ok(Atom(Ty(Boolean))),
+	    Some(Sym(s)) if s.starts_with("..") =>
+		Ok(Atom(RestPat(s.strip_prefix("..").unwrap().to_string()))),
 	    Some(Sym(s))                  => Ok(Atom(Var(s))),
 	    Some(ParClose) => break,
 	    Some(ParOpen)  => {
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
+	}
+    }
+}
diff --git a/src/sexp/display.rs b/src/sexp/display.rs
index eff3904..9f54efe 100644
--- a/src/sexp/display.rs
+++ b/src/sexp/display.rs
@@ -25,11 +25,13 @@ impl fmt::Display for SLeaf {
             False  => "false".to_string(),
             Int(x) => x.to_string(),
             Var(s) => s.to_string(),
+	    RestPat(s) => format!("..{s}"),
             Quote  => "quote".to_string(),
             Vector => "vector".to_string(),
 	    Print  => "print".to_string(),
             Let    => "let".to_string(),
 	    Fun    => "fn".to_string(),
+	    Case   => "case".to_string(),
 	    Ty(t)  => t.to_string(),
 	    Arr    => "->".to_string(),
             Nil    => "()".to_string(),
diff --git a/src/sexp/mod.rs b/src/sexp/mod.rs
index 4bb4fa2..ba8743f 100644
--- a/src/sexp/mod.rs
+++ b/src/sexp/mod.rs
@@ -3,6 +3,7 @@ pub mod step;
 pub mod util;
 pub mod subst;
 pub mod display;
+pub mod case;
 
 use crate::r#type::Type;
 
@@ -37,6 +38,8 @@ pub enum SLeaf {
 
     Fun,
 
+    Case,
+
     Ty(Type),
     Arr,
 
@@ -47,6 +50,7 @@ pub enum SLeaf {
     False,
 
     Var(String),
+    RestPat(String),
 
     Nil,
 }
@@ -84,6 +88,7 @@ impl SExp {
                     && b.consists_of_values()
                 ),
             Atom(Var(_)) => false,
+            Atom(RestPat(_)) => false,
             Atom(_) => true,
         }
     }
diff --git a/src/type/check.rs b/src/type/check.rs
index d815c85..b2815c7 100644
--- a/src/type/check.rs
+++ b/src/type/check.rs
@@ -233,6 +233,8 @@ impl SExp {
 	    Atom(Ty(_))  => Ok(TypeLit),
 	    Atom(Arr)    => Ok(arr(List(vec![TypeLit, TypeLit]), TypeLit)),
 	    Atom(Fun)    => Err(FunAsAtom),
+	    Atom(Case)   => todo!(),
+	    Atom(RestPat(_)) => todo!(),
 
             SCons(op, l) => {