From 6ce77dfc296c24d43ac1e3b2daffec0a7e485891 Mon Sep 17 00:00:00 2001 From: Joel Kronqvist Date: Mon, 18 Aug 2025 13:38:57 +0300 Subject: refactor: change conversions to use a stricter function with deduplicated code --- src/type/conversion.rs | 492 ++++++++++--------------------------------------- 1 file changed, 96 insertions(+), 396 deletions(-) (limited to 'src/type/conversion.rs') diff --git a/src/type/conversion.rs b/src/type/conversion.rs index 1d14971..844632f 100644 --- a/src/type/conversion.rs +++ b/src/type/conversion.rs @@ -4,309 +4,86 @@ use std::collections::HashMap; impl Type { - /// Checks if this type is known as the given other type, - /// ie. checks if there exists an implicit conversion from - /// one to the other. - /// - /// This is needed for list to vec conversions. - /// ```rust - /// use myslip::r#type::{Type::*, util::*}; - /// assert!(List(vec![Integer, Integer, Integer]).aka(&vecof(Integer))); - /// ``` - /// - /// Preferrably this should also work with generics: - /// ```rust - /// use myslip::r#type::{Type::*, util::*}; - /// assert!(List(vec![Integer, Integer, Integer]).aka(&vecof(vt("T")))); - /// assert!(List(vec![Boolean, Boolean, Boolean]).aka(&vecof(vt("T")))); - /// ``` - /// - /// Also, because quotes and vectors have their operators hanging - /// with them, having a conversion (Vector/Quote X) -> X is convenient. - /// ```rust - /// use myslip::r#type::{Type::*, util::*}; - /// assert!( - /// List(vec![QuoteTy, List(vec![Integer, Integer])]).aka(&vecof(Integer)), - /// ); - /// assert!( - /// List(vec![List(vec![QuoteTy, List(vec![Integer, Integer])])]).aka(&vecof(Integer)), - /// ); - /// ``` - /// - /// But of course it also should know when to fail: - /// ```rust - /// use myslip::r#type::{Type::*, util::*}; - /// assert!(!List(vec![Integer, Boolean]).aka(&vecof(Integer))); - /// assert!(!List(vec![Integer, Boolean]).aka(&vecof(Boolean))); - /// ``` - /// - /// Generics might be dangerous: - /// ```rust - /// use myslip::r#type::{Type::*, util::*}; - /// assert!(arr(Boolean, Boolean).aka(&arr(vt("T"), vt("T")))); - /// assert!( - /// List(vec![Integer, Integer]) - /// .aka(&List(vec![vt("T"), vt("T")])) - /// ); - /// assert!( - /// List(vec![Integer, Boolean]) - /// .aka(&List(vec![vt("T"), vt("H")])) - /// ); - /// assert!( - /// !List(vec![Integer, Boolean]) - /// .aka(&List(vec![vt("T"), vt("T")])) - /// ); - /// assert!( - /// !List(vec![Integer, Boolean]) - /// .aka(&List(vec![vt("T"), vt("T")])) - /// ); - /// assert!(!List(vec![Integer, Boolean, vt("X")]).aka(&vecof(vt("T")))); - /// ``` - pub fn aka(&self, known_as: &Type) -> bool { - self.least_general_supertype(known_as) == *known_as - } - pub fn least_general_supertype(&self, other: &Type) -> Type { - let (ty, ctx) = self.lgst_ctx(other, Vec::new()); + /// Tries to convert this type into another type. + /// + /// The following conversions are required: + /// 0. self == other => self + /// 1. (T T ... T T) -> (T ...) + /// 2. self = concrete and other = variable type => self, + /// 3. arrow types and lists are mapped + pub fn convert(self, other: &Type) -> Result { + let (ty, ctx) = self.convert_ctx(other)?; let mut checks = HashMap::new(); for (name, ty1) in ctx { if let Some(ty2) = checks.insert(name, ty1.clone()) { if ty2 != ty1 { - return vt("?"); + return Err(()); } } } - ty + Ok(ty) } - fn lgst_ctx( - &self, - other: &Type, - mut ctx: Vec<(String, Type)> - ) -> (Type, Vec<(String, Type)>) { + fn convert_ctx( + self, + other: &Type + ) -> Result<(Type, Vec<(String, Type)>), ()> { - match (self, other) { - - (a, b) if a == b => (a.clone(), ctx), - - (a, VarType(name)) => { - ctx.push((name.clone(), a.clone())); - (vt(name), ctx) - }, - - (List(v), b) if v.len() == 1 && *&v[0].aka(b) => (b.clone(), ctx), + let mut ctx = vec![]; - (List(v1), x) if !x.is_quoted_or_vectored_list() - && (v1.get(0) == Some(&VecType) || v1.get(0) == Some(&QuoteTy)) - && v1.get(1) != None => - { - match (v1.get(1), x) { - (Some(a), b) => { - let res = a.lgst_ctx(&b, ctx); - res - }, - _ => panic!("unreachable") - } - }, + match (self, other) { - (VecOf(_), VecOf(b)) => { - match &**b { - VarType(s) => (vecof(vt(s)), ctx), - _ => (vt("T"), ctx) - } - }, + (a, b) if a == *b => Ok((a, ctx)), - (Arrow(a1, a2), Arrow(b1, b2)) => { - let (t1, newctx) = a1.lgst_ctx(b1, ctx); - ctx = newctx; - let (t2, newctx) = a2.lgst_ctx(b2, ctx); - ctx = newctx; - (arr(t1, t2), ctx) + (ty, VarType(name)) => if ty.is_concrete().is_ok() { + ctx.push((name.clone(), ty.clone())); + Ok((ty, ctx)) + } else { + Err(()) }, - (List(v1), List(v2)) if v1.len() == v2.len() => { - let mut res = vec![]; - for (a, b) in v1.into_iter().zip(v2) { - let (ty, newctx) = a.lgst_ctx(b, ctx.clone()); - res.push(ty); - ctx = newctx; - } - (List(res), ctx) - }, - - (List(v1), List(v2)) => match v1.get(0).or(v2.get(0)) { - Some(first) => { - let mut res = first.clone(); - for ty in v1.into_iter().chain(v2) { - let (ty, newctx) = res.lgst_ctx(ty, ctx.clone()); - res = ty; - ctx = newctx; - } - (vecof(res), ctx) - }, - None => panic!("unreachable - types would be equal") - }, - - (List(v), VecOf(b)) => { - let mut res = *b.clone(); - for ty in v { - let (ty, newctx) = res.lgst_ctx(ty, ctx.clone()); - res = ty; - ctx = newctx; - } - (vecof(res), ctx) - }, - (VecOf(b), List(v)) => { - let mut res = *b.clone(); - for ty in v { - let (ty, newctx) = res.lgst_ctx(ty, ctx.clone()); - res = ty; - ctx = newctx; + let mut res = vec![]; + for (t1, t2) in v1.into_iter().zip(v2) { + let (t, newctx) = t1.convert_ctx(t2)?; + ctx.extend(newctx); + res.push(t); } - (vecof(res), ctx) + Ok((List(res), ctx)) }, - _ => (vt("T"), ctx) - - } - - } - - /// Tries to convert this type into a subtype of the other. - /// - /// Currently the most important conversion is from list to vec. - /// ```rust - /// use myslip::r#type::{Type::*, util::*}; - /// - /// assert_eq!(Integer.into_type(&Boolean), Err(())); - /// assert_eq!(Integer.into_type(&Integer), Ok(Integer)); - /// assert_eq!(Integer.into_type(&vt("T")), Ok(Integer)); - /// assert_eq!( - /// List(vec![Integer, Integer]).into_type(&vecof(Integer)), - /// Ok(vecof(Integer)) - /// ); - /// assert_eq!( - /// List(vec![Integer, Integer]).into_type(&vecof(vt("T"))), - /// Ok(vecof(Integer)) - /// ); - /// assert_eq!( - /// List(vec![Integer, Boolean]).into_type(&vecof(vt("T"))), - /// Ok(vecof(vt("T"))) - /// ); - /// assert_eq!(List(vec![Boolean, Integer, Integer]).into_type(&List(vec![Boolean, vt("T"), vt("T")])), Ok(List(vec![Boolean, Integer, Integer]))) - /// ``` - /// - /// Though the conversion from (a) to a is also convenient: - /// ```rust - /// use myslip::r#type::{Type::*, util::*}; - /// - /// assert_eq!(List(vec![Integer]).into_type(&Integer), Ok(Integer)); - /// ``` - /// - /// Also, because quotes and vectors have their operators hanging - /// with them, having a conversion (Vector/Quote X) -> X is convenient. - /// ```rust - /// use myslip::r#type::{Type::*, util::*}; - /// assert_eq!( - /// List(vec![VecType, vecof(Integer)]).into_type(&vecof(Integer)), - /// Ok(vecof(Integer)) - /// ); - /// assert_eq!( - /// List(vec![List(vec![VecType, vecof(Integer)])]).into_type(&vecof(Integer)), - /// Ok(vecof(Integer)) - /// ); - /// ``` - /// - /// Now this also needs to be able to hand generics: - /// ```rust - /// use myslip::r#type::{Type::*, util::*}; - /// assert_eq!( - /// arr(Boolean, Boolean) - /// .into_type(&arr(vt("T"), vt("T"))), - /// Ok(arr(Boolean, Boolean)) - /// ); - /// assert_eq!( - /// arr(Boolean, Integer) - /// .into_type(&arr(vt("T"), vt("H"))), - /// Ok(arr(Boolean, Integer)) - /// ); - /// assert_eq!( - /// arr(Boolean, Integer) - /// .into_type(&arr(vt("T"), vt("T"))), - /// Err(()) - /// ); - /// assert_eq!( - /// List(vec![Integer, Integer]) - /// .into_type(&List(vec![vt("T"), vt("T")])), - /// Ok(List(vec![Integer, Integer])) - /// ); - /// assert!( - /// List(vec![Integer, Boolean]) - /// .into_type(&List(vec![vt("T"), vt("T")])) - /// .is_err() - /// ); - /// assert!( - /// List(vec![Integer, Boolean, vt("X")]) - /// .into_type(&vecof(vt("T"))) - /// .is_err() - /// ); - /// ``` - pub fn into_type(self, other: &Type) -> Result { - if !self.aka(other) { - return Err(()); - } - - match (&self, other) { - - (a, b) if a == b => Ok(self), - - (_, VarType(_)) => Ok(self), - - (List(x), b) if x.len() == 1 && *&x[0].aka(b) => Ok(x[0].clone().into_type(b)?), - (Arrow(a1, a2), Arrow(b1, b2)) => { - let t1 = a1.clone().into_type(b1)?; - let t2 = a2.clone().into_type(b2)?; - Ok(arr(t1, t2)) + let (t1, newctx) = a1.convert_ctx(b1)?; + ctx.extend(newctx); + let (t2, newctx) = a2.convert_ctx(b2)?; + ctx.extend(newctx); + Ok((arr(t1, t2), ctx)) }, - (List(v), x) if !x.is_quoted_or_vectored_list() - && (v.get(0) == Some(&VecType) || v.get(0) == Some(&QuoteTy)) - && v.get(1) != None => - { - v[1].clone().into_type(x) + (List(v), VecOf(ty)) => match v.get(0) { + Some(t) => { + let (convt, newctx) = t.clone().convert_ctx(ty)?; + ctx.extend(newctx); + for t in v { + let (sconvt, newctx) = t.convert_ctx(ty)?; + if sconvt != convt { + return Err(()); + } else { + ctx.extend(newctx); + } + } + Ok((vecof(convt), ctx)) + }, + None => Err(()), // questionable? could be useful to convert? }, - (VecOf(a), VecOf(b)) => Ok(vecof(a.clone().into_type(&b)?)), - - (List(v1), List(v2)) if v1.len() == v2.len() => { - let mut res = vec![]; - for (t1, t2) in v1.into_iter().zip(v2) { - res.push(t1.clone().into_type(&t2)?); - } - Ok(List(res)) + (VecOf(t1), VecOf(t2)) => { + let (convt, ctx) = t1.convert_ctx(t2)?; + Ok((vecof(convt), ctx)) }, - (List(v), VecOf(b)) => match v.get(0) { - Some(first) => { - let cand = v.into_iter() - .fold(first.clone(), |a, b| a.least_general_supertype(b)); - if cand.aka(b) { - Ok(vecof(cand)) - } else { - Err(()) - } - }, - None => if NilType.aka(b) { - Ok(vecof(NilType)) - } else { - Err(()) - }, - }, - _ => Err(()) - } } @@ -318,155 +95,78 @@ mod tests { use crate::r#type::{Type::*, util::*}; #[test] - fn test_basic_general_supertypes() { - + fn test_conversion_case0() { + assert_eq!(Integer.convert(&Integer), Ok(Integer)); + assert_eq!(Boolean.convert(&Boolean), Ok(Boolean)); assert_eq!( - Integer.least_general_supertype(&Integer), - Integer, - "if two types are equal, they get the same supertype" + List(vec![Integer, Boolean]) + .convert(&List(vec![Integer, Boolean])), + Ok(List(vec![Integer, Boolean])) ); assert_eq!( - Integer.least_general_supertype(&Boolean), - vt("T"), - "if two types have nothing in common, vt(\"t\") is returned" - ); - - } - - #[test] - fn test_compound_general_supertypes() { - - assert_eq!( - List(vec![Integer, Integer]) - .least_general_supertype( - &List(vec![Integer, Integer]) - ), - List(vec![Integer, Integer]) + vecof(Integer).convert(&vecof(Integer)), + Ok(vecof(Integer)) ); + assert_eq!(vt("T").convert(&vt("T")), Ok(vt("T"))); - assert_eq!( + assert!(Integer.convert(&Boolean).is_err()); + assert!(Boolean.convert(&Integer).is_err()); + assert!( List(vec![Integer, Boolean]) - .least_general_supertype( - &List(vec![Integer, Integer]) - ), - List(vec![Integer, vt("T")]) + .convert(&List(vec![Integer, Integer])) + .is_err() ); - - assert_eq!( - vecof(Integer) - .least_general_supertype( - &vecof(Integer) - ), + assert!( vecof(Integer) + .convert(&vecof(Boolean)) + .is_err() ); - - assert_eq!( - vecof(Integer) - .least_general_supertype( - &vecof(Boolean) - ), - vt("T") - ); - - assert_eq!( - List(vec![Integer, Boolean]).least_general_supertype( - &List(vec![Boolean, Integer]) - ), - List(vec![vt("T"), vt("T")]) - ); - - assert_eq!( - vecof(Integer).least_general_supertype(&vecof(vt("T"))), - vecof(vt("T")) - ); - + assert!(vt("T").convert(&vt("H")).is_err()); } #[test] - fn test_removing_quote_and_vec() { - assert_eq!( - List(vec![List(vec![VecType, NilType])]).least_general_supertype(&NilType), - NilType - ); + fn test_conversion_case1() { assert_eq!( - List(vec![VecType, NilType]).least_general_supertype(&NilType), - NilType + List(vec![Integer]).convert(&vecof(Integer)), + Ok(vecof(Integer)) ); assert_eq!( - List(vec![QuoteTy, NilType]).least_general_supertype(&NilType), - NilType - ); - assert_eq!( - List(vec![VecType, vecof(Boolean)]) - .least_general_supertype( - &vecof(Boolean) - ), - vecof(Boolean) - ); - assert_eq!( - List(vec![List(vec![VecType, vecof(Boolean)])]) - .least_general_supertype( - &vecof(Boolean) - ), - vecof(Boolean) - ); - assert_eq!( - List(vec![QuoteTy, List(vec![Integer, Boolean])]) - .least_general_supertype( - &List(vec![Integer, Boolean]) - ), - List(vec![Integer, Boolean]) + List(vec![Integer]).convert(&vecof(vt("T"))), + Ok(vecof(Integer)) ); } #[test] - fn test_conversion_in_general_supertypes() { - - assert_eq!( - List(vec![Integer, Integer]).least_general_supertype( - &vecof(Integer) - ), - vecof(Integer) - ); - + fn test_conversion_case2() { + assert_eq!(Integer.convert(&vt("T")), Ok(Integer)); + assert_eq!(Boolean.convert(&vt("T")), Ok(Boolean)); assert_eq!( - List(vec![Integer, Integer]).least_general_supertype( - &List(vec![Integer, Integer, Integer]) - ), - vecof(Integer) + List(vec![Integer, Integer]) + .convert(&List(vec![vt("T"), vt("T")])), + Ok(List(vec![Integer, Integer])) ); - assert_eq!( - List(vec![Integer, Boolean]).least_general_supertype( - &List(vec![Integer, Boolean, Integer]) - ), - vecof(vt("T")) + List(vec![Integer, Boolean]) + .convert(&List(vec![vt("T"), vt("H")])), + Ok(List(vec![Integer, Boolean])) ); - + assert_eq!(vecof(Integer).convert(&vecof(vt("T"))), Ok(vecof(Integer))); assert_eq!( - List(vec![Boolean, Integer]).least_general_supertype( - &vecof(Integer) - ), - vecof(vt("T")) + arr(arr(vecof(Integer), Integer), arr(vecof(Integer), Integer)) + .convert(&arr(vt("T"), vt("T"))), + Ok(arr(arr(vecof(Integer), Integer), arr(vecof(Integer), Integer))) ); - assert_eq!( - List(vec![VecType, vecof(Integer)]).least_general_supertype( - &vecof(vt("T")) - ), - vecof(vt("T")) + assert!( + List(vec![Integer, Boolean]) + .convert(&List(vec![vt("T"), vt("T")])) + .is_err() ); - - assert_eq!( - List(vec![ - List(vec![VecType, vecof(Integer)]), - List(vec![VecType, vecof(Integer)]) - ]).least_general_supertype( - &List(vec![vecof(vt("T")), vecof(vt("T"))]) - ), - List(vec![vecof(vt("T")), vecof(vt("T"))]) + assert!( + arr(arr(vecof(Integer), Integer), arr(vecof(Boolean), Integer)) + .convert(&arr(vt("T"), vt("T"))) + .is_err() ); - } } -- cgit v1.2.3