Changed UndefinedType to VarType(String) for generics and added tests for inferring them.

Inferring is done by method Type::infer_generics.
Whether it is executed is controlled by method Type::is_concrete.
Also had to change the Display for Type and its tests,
as the enum variants changed.

3 files changed, 134 insertions, 6 deletions

diff --git a/src/type/check.rs b/src/type/check.rs
index 8d2a35d..6e7e557 100644
--- a/src/type/check.rs
+++ b/src/type/check.rs
@@ -131,11 +131,16 @@ impl SExp {
             Atom(Nil)   => Ok(List(vec![])),
             Atom(Quote) => Ok(List(vec![])), // TODO make it all identity functions
 
-            SCons(op, l) if **op == Atom(Quote) => (*l).infer_list_type(ctx),
-
             SCons(op, l) => {
                 let opertype = (*op).infer_type(ctx.clone())?;
                 let argstype =  (*l).infer_list_type(ctx)?;
+
+                let opertype = if opertype.is_concrete() {
+                    opertype
+                } else {
+                    opertype.infer_generics(&argstype)?
+                };
+
                 match (opertype, argstype) {
                     (Arrow(a, b), c) => {
                         if *a != c {
@@ -150,7 +155,10 @@ impl SExp {
                     },
                     (t, _) => Err(InvalidOperator {
                         operator: *op.clone(),
-                        expected: arr(UndefinedType, UndefinedType),
+                        expected: arr(
+                            VarType(String::from("_")),
+                            VarType(String::from("_"))
+                        ),
                         found:    t,
                     }),
                 }
@@ -169,3 +177,86 @@ impl SExp {
     }
 
 }
+
+
+impl Type {
+
+    /// Infers the type of generic 'VarType's using type of arguments.
+    ///
+    /// In case there generic variables that can't be inferred,
+    /// returns an TypeError::UnboundVariable.
+    fn infer_generics(self, argtype: &Type) -> Result<Type, TypeError> {
+        todo!()
+    }
+
+}
+
+
+#[cfg(test)]
+mod tests {
+    use super::{*, Type::*, TypeError};
+    use crate::r#type::util::*;
+
+    #[test]
+    fn test_failing_infer_generics() {
+        assert_eq!(
+            arr(Integer, VarType("X".to_string())).infer_generics(&Integer),
+            Err(TypeError::UnboundGeneric(String::from("X")))
+        );
+    }
+
+    #[test]
+    fn test_infer_generics() {
+
+        // Simple identity function, really all we
+        // care about (this language doesn't attempt
+        // to have useful generic programming capabilities,
+        // but some simple features are required for typing
+        // quotes)...
+        assert_eq!(
+            arr(VarType("T".to_string()), VarType("T".to_string())).infer_generics(&Integer),
+            Ok(arr(Integer, Integer))
+        );
+
+        // ...but let's make it work for other simple cases too,
+        // maybe someone finds use for these.
+        assert_eq!(
+            arr(
+                    List(vec![Integer, VarType("T".to_string())]),
+                    List(vec![VarType("T".to_string()), Integer])
+                ).infer_generics(
+                    &List(vec![Integer, arr(Integer, Integer)])
+                ),
+            Ok(arr(
+                List(vec![Integer, arr(Integer, Integer)]),
+                List(vec![arr(Integer, Integer), Integer])
+            ))
+        );
+
+        assert_eq!(
+            arr(VarType("T".to_string()), Integer).infer_generics(&List(vec![Integer])),
+            Ok(arr(List(vec![Integer]), Integer))
+        );
+
+        assert_eq!(
+            arr(List(vec![VarType("A".to_string()), VarType("B".to_string())]), VarType("B".to_string()))
+                .infer_generics(&List(vec![Integer, arr(Integer, Integer)])),
+            Ok(arr(
+                    List(vec![List(vec![Integer, arr(Integer, Integer)])]),
+                    arr(Integer, Integer)
+                ))
+        );
+
+        assert_eq!(
+            arr(
+                arr(VarType("A".to_string()), VarType("B".to_string())),
+                arr(VarType("B".to_string()), VarType("A".to_string()))
+            ).infer_generics(&arr(Integer, arr(Integer, Integer))),
+            Ok(arr(
+                arr(Integer, arr(Integer, Integer)),
+                arr(arr(Integer, Integer), Integer)
+            ))
+        );
+
+    }
+}
diff --git a/src/type/display.rs b/src/type/display.rs
index 781d614..be51858 100644
--- a/src/type/display.rs
+++ b/src/type/display.rs
@@ -26,7 +26,7 @@ impl fmt::Display for Type {
                                     .collect::<Vec<String>>()
                                     .join(" ")
                            ),
-            UndefinedType => write!(f, "?"),
+            VarType(name) => write!(f, "{}", name),
         }
     }
 }
@@ -47,7 +47,7 @@ impl fmt::Display for TypeError {
     /// assert_eq!(
     ///     InvalidOperator {
     ///         operator: Atom(Int(1)),
-    ///         expected: arr(UndefinedType, UndefinedType),
+    ///         expected: arr(VarType("?".to_string()), VarType("?".to_string())),
     ///         found:    Integer
     ///     }.to_string(),
     ///     "invalid operator: '1'\nexpected: '? -> ?'\nfound: 'Int'".to_string()
@@ -60,10 +60,15 @@ impl fmt::Display for TypeError {
     ///     }.to_string(),
     ///     "invalid argument list: '(1 2 3)'\nexpected: '(Int Int)'\nfound: '(Int Int Int)'".to_string()
     /// );
+    /// assert_eq!(
+    ///     UnboundGeneric(String::from("?")).to_string(),
+    ///     "unbound generic type: '?'".to_string()
+    /// );
     /// ```
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
         match self {
             UndefinedVariable(name) => write!(f, "undefined variable: '{}'", name),
+            UnboundGeneric(name)    => write!(f, "unbound generic type: '{}'", name),
             InvalidOperator { operator, expected, found } => {
                 write!(
                     f,
diff --git a/src/type/mod.rs b/src/type/mod.rs
index 5e7076a..6c4be97 100644
--- a/src/type/mod.rs
+++ b/src/type/mod.rs
@@ -17,7 +17,10 @@ pub enum Type {
 
     List(Vec<Type>),
 
-    UndefinedType, // only for errors
+    /// Type for generics
+    /// and also error messages
+    /// with unknown types
+    VarType(String),
 
 }
 
@@ -27,6 +30,8 @@ pub enum TypeError {
 
     UndefinedVariable(String),
 
+    UnboundGeneric(String),
+
     InvalidOperator {
 	operator: SExp,
 	expected: Type,
@@ -41,3 +46,30 @@ pub enum TypeError {
 
     OtherError
 }
+
+
+impl Type {
+    /// Tests if the type has no variable types.
+    ///
+    /// **Examples**
+    /// ```rust
+    /// use melisp::r#type::{*, Type::*, TypeError::*, util::*};
+    ///
+    /// assert!(Integer.is_concrete());
+    /// assert!(!VarType("a".to_string()).is_concrete());
+    ///
+    /// assert!(arr(Integer, Integer).is_concrete());
+    /// assert!(!arr(VarType("b".to_string()), Integer).is_concrete());
+    ///
+    /// assert!(
+    ///     List(vec![Integer, Integer, arr(Integer, Integer)]).is_concrete()
+    /// );
+    /// assert!(
+    ///     !List(vec![Integer, VarType("a".to_string()), Integer])
+    ///         .is_concrete()
+    /// );
+    /// ```
+    pub fn is_concrete(&self) -> bool {
+        todo!()
+    }
+}