use crate::r#type::{Type, TypeError, Type::*, TypeError::*, PatFail::*, util::*}; use crate::sexp::{SExp, SExp::*, SLeaf::*}; use std::collections::{HashMap, HashSet}; use std::iter; impl SExp { /// Checks if this pattern sexp can match the given type, /// returns all variable names bound by a respective case. pub fn matches_type( &self, ty: &Type ) -> Result, TypeError> { let mut checks = HashSet::new(); let res = self.clone() .matches_type_ctx(ty.clone(), HashMap::new())?; for (k, _) in res.clone() { if !checks.insert(k.clone()) { return Err(InvalidPattern(RepeatedVariable(k, self.clone()))); } } Ok(res) } fn matches_type_ctx( self, ty: Type, ctx: HashMap ) -> Result, TypeError> { match (self, ty) { (Atom(Var(name)), ty) => Ok(ctx.into_iter().chain(iter::once((name, ty))).collect()), (s, ty) if s.infer_type(ctx.clone()) == Ok(ty.clone()) => Ok(ctx.into_iter().collect()), (se, List(v)) if v.get(0) == Some(&VecType) => match (&se, v.get(1)) { (_, None) => Err(OtherError), (SCons(_, _), Some(VecOf(ty))) => { let mut res: Vec<(String, Type)> = ctx.clone().into_iter().collect(); let mut exps = se.parts(); let restpat = exps.remove(exps.len() - 1); for exp in exps { match exp { Atom(Var(name)) => res.push((name, *ty.clone())), lit => { lit.matches_type_ctx(*ty.clone(), ctx.clone())?; } } } match restpat { Atom(Var(name)) => res.push((name, *ty.clone())), Atom(RestPat(name)) => res.push( (name, List(vec![VecType, vecof(*ty.clone())])) ), lit => { lit.matches_type_ctx(*ty.clone(), ctx)?; } } Ok(res) }, (Atom(Nil), Some(VecOf(_))) => Ok(ctx.into_iter().collect()), _ => Err(OtherError), }, (se, List(v)) if v.get(0) == Some(&QuoteTy) => match (&se, v.get(1)) { (_, None) => Err(OtherError), (SCons(_, _), Some(List(types))) => { let mut res = vec![]; let exps = //if types.len() == 1 { //vec![se.clone()] //} else { se.clone().parts() /*}*/; if exps.len() == types.len() { for (exp, ty) in exps.into_iter().zip(types) { for et in exp.matches_type_ctx(ty.clone(), ctx.clone() )? { res.push(et); } } Ok(res) } else { match exps.last().cloned() { Some(Atom(RestPat(name))) => { for (exp, ty) in exps.clone() .into_iter() .rev().skip(1).rev() .zip(types.clone()) { for (e, t) in exp.matches_type_ctx(ty, ctx.clone())? { res.push((e, t)); } } res.push(( name, List(vec![QuoteTy, List(types .clone() .into_iter() .skip(exps.len() - 1) .collect())]) )); Ok(res) }, _ => Err(InvalidPattern(TypeMismatch { pattern: se.clone(), expected: List(vec![QuoteTy, List(types.to_vec())]), found: List(vec![QuoteTy, se.infer_list_type(ctx)?]), })), } } }, (Atom(Nil), Some(List(v))) if v.len() == 0 => Ok(ctx.into_iter().collect()), _ => Err(OtherError) }, (se, SumType(l, r)) => match (&(se.parts())[..], (*l, *r)) { ([op, exp], (l, _)) if *op == Atom(Inl) => exp.clone().matches_type_ctx(l, ctx.clone()), ([op, exp], (_, r)) if *op == Atom(Inr) => exp.clone().matches_type_ctx(r, ctx.clone()), _ => Err(OtherError), }, _ => Err(OtherError), // maybe add nicer error? } } } #[cfg(test)] mod tests { use crate::sexp::{SExp::*, SLeaf::*, util::*}; use crate::r#type::{Type::*, util::*, TypeError::*, PatFail::*}; #[test] fn test_type_atoms() { assert_eq!(Atom(Int(1)).matches_type(&Integer), Ok(vec![])); assert_eq!(Atom(True).matches_type(&Boolean), Ok(vec![])); assert_eq!(Atom(Ty(Integer)).matches_type(&TypeLit), Ok(vec![])); assert_eq!(Atom(Nil).matches_type(&NilType), Ok(vec![])); } #[test] fn test_vector_match() { assert_eq!( scons(1, scons(2, Nil)) .matches_type(&List(vec![VecType, vecof(Integer)])), Ok(vec![]) ); assert_eq!( scons(var("a"), scons(var("b"), Nil)) .matches_type(&List(vec![VecType, vecof(Integer)])), Ok(vec![ ("a".to_string(), Integer), ("b".to_string(), Integer) ]) ); assert_eq!( scons(var("a"), scons(RestPat("b".to_string()), Nil)) .matches_type(&List(vec![VecType, vecof(Integer)])), Ok(vec![ ("a".to_string(), Integer), ("b".to_string(), List(vec![VecType, vecof(Integer)])) ]) ); } #[test] fn test_list_match() { assert_eq!( scons(1, scons(2, Nil)) .matches_type(&List(vec![QuoteTy, List(vec![Integer, Integer])])), Ok(vec![]) ); assert_eq!( scons(var("a"), scons(var("b"), Nil)) .matches_type(&List(vec![QuoteTy, List(vec![Integer, Integer])])), Ok(vec![ ("a".to_string(), Integer), ("b".to_string(), Integer) ]) ); assert_eq!( scons(var("a"), scons(RestPat("b".to_string()), Nil)) .matches_type(&List(vec![QuoteTy, List(vec![Integer, Integer, Integer])])), Ok(vec![ ("a".to_string(), Integer), ("b".to_string(), List(vec![QuoteTy, List(vec![Integer, Integer])])) ]) ); } #[test] fn test_mismatch_match() { assert_eq!( scons(1, scons(2, Nil)) .matches_type(&List(vec![QuoteTy, List(vec![Integer])])), Err(InvalidPattern(TypeMismatch { pattern: scons(1, scons(2, Nil)), expected: List(vec![QuoteTy, List(vec![Integer])]), found: List(vec![QuoteTy, List(vec![Integer, Integer])]) })) ); } #[test] fn test_simple_wildcard_match() { assert_eq!( var("x").matches_type(&List(vec![QuoteTy, List(vec![Integer, Integer])])), Ok(vec![("x".to_string(), List(vec![QuoteTy, List(vec![Integer, Integer])]))]) ); } #[test] fn test_invalid_pattern_match() { assert_eq!( scons(var("x"), scons(var("x"), Nil)) .matches_type(&List(vec![QuoteTy, List(vec![Integer, Integer])])), Err(InvalidPattern(RepeatedVariable( "x".to_string(), scons(var("x"), scons(var("x"), Nil)) ))) ); } #[test] fn test_nil_match() { assert_eq!( Atom(Nil).matches_type(&List(vec![VecType, vecof(Boolean)])), Ok(vec![]) ); assert_eq!( Atom(Nil).matches_type(&List(vec![QuoteTy, List(vec![])])), Ok(vec![]) ); } #[test] fn test_sumtype_match() { assert_eq!( scons(Inl, scons(var("x"), Nil)).matches_type(&sumtype(Integer, Boolean)), Ok(vec![("x".to_string(), Integer)]) ); assert_eq!( scons(Inr, scons(var("x"), Nil)).matches_type(&sumtype(Integer, Boolean)), Ok(vec![("x".to_string(), Boolean)]) ); assert!( scons(Inl, scons(True, Nil)).matches_type(&sumtype(Integer, Boolean)).is_err() ); assert!( scons(Inr, scons(1, Nil)).matches_type(&sumtype(Integer, Boolean)).is_err() ); } }