Merge remote-tracking branch 'origin/main' into move-testsmove-tests

9 files changed, 321 insertions, 52 deletions

diff --git a/progs/tests/func/wrong_params.sy b/progs/tests/func/wrong_params.sy
index e49e89b..0082a3a 100644
--- a/progs/tests/func/wrong_params.sy
+++ b/progs/tests/func/wrong_params.sy
@@ -4,4 +4,4 @@ start :: fn {
     f
 }
 
-// errors: [ErrorKind::TypeMismatch(_, _), ErrorKind::TypeMismatch(Type::Void, Type::Int)]
+// errors: [ErrorKind::TypeMismatch(_, _), ErrorKind::TypeMismatch(Type::Int, Type::Void)]
diff --git a/progs/tests/nullable_types.sy b/progs/tests/nullable_types.sy
new file mode 100644
index 0000000..2088c53
--- /dev/null
+++ b/progs/tests/nullable_types.sy
@@ -0,0 +1,33 @@
+test001 :: fn -> int {
+    a : int? = nil
+    a = 2
+    ret a
+}
+
+test002 :: fn b:bool -> int? {
+    if b {
+        ret nil
+    } else {
+        ret 0
+    }
+}
+
+// TODO(ed): Introduce type type!
+test003 :: fn {
+    a := test002! false
+    a += 1
+    a <=> 1
+}
+
+
+start :: fn {
+    test001!
+    nil <=> test002! true
+    0 <=> test002! false
+    q : bool? = true
+    q <=> true
+    q = nil
+    q <=> nil
+    test003!
+}
+
diff --git a/progs/tests/tuple/sub.sy b/progs/tests/tuple/sub.sy
index e5d60f2..cca4f2c 100644
--- a/progs/tests/tuple/sub.sy
+++ b/progs/tests/tuple/sub.sy
@@ -1,3 +1,4 @@
 start :: fn {
-    (1, -2, 3, -4) - (4, 3, -2, -1) <=> (-3, 1, 1, -5)
+    print (1, -2, 3, -4) - (4, 3, -2, -1)
+    (1, -2, 3, -4) - (4, 3, -2, -1) <=> (-3, -5, 5, -3)
 }
diff --git a/progs/tests/union_types_simple.sy b/progs/tests/union_types_simple.sy
new file mode 100644
index 0000000..f6cf622
--- /dev/null
+++ b/progs/tests/union_types_simple.sy
@@ -0,0 +1,36 @@
+f :: fn a:bool -> int | str | void {
+    if a {
+        ret 1
+    } else {
+        ret
+    }
+}
+
+g :: fn a:bool -> int | (bool, bool) {
+    if a {
+        ret 1
+    } else {
+        ret (true, true)
+    }
+}
+
+h :: fn a:bool -> int | fn -> int {
+    if a {
+        f :: fn -> int { ret 1 }
+        ret f
+    } else {
+        ret 1
+    }
+}
+
+start :: fn {
+    1 <=> f! true
+    nil <=> f! false
+    (true, true) <=> g! false
+    1 <=> g! true
+    f(true) <=> g(true)
+
+    1 <=> h! false
+    q :: h! true
+    1 <=> q()
+}
diff --git a/progs/tests/union_types_simple_faulty.sy b/progs/tests/union_types_simple_faulty.sy
new file mode 100644
index 0000000..b742054
--- /dev/null
+++ b/progs/tests/union_types_simple_faulty.sy
@@ -0,0 +1,25 @@
+f :: fn a:bool -> int | void {
+    if a {
+        ret 1
+    } else {
+        ret "hello!"
+    }
+}
+
+g :: fn a:bool -> int | (bool, bool) {
+    if a {
+        ret 1
+    } else {
+        ret (true, 1.0)
+    }
+}
+
+start :: fn {
+    0 <=> f! true
+    0.0 <=> f! false
+    ("hello!", "there") <=> g! false
+    1 <=> g! true
+    f(true) <=> g(true)
+}
+
+// errors: [ ErrorKind::TypeMismatch(_, _), ErrorKind::TypeMismatch(_, _), ErrorKind::TypeError(_, _), ErrorKind::TypeError(_, _) ]
diff --git a/src/compiler.rs b/src/compiler.rs
index b45d47e..9ab868f 100644
--- a/src/compiler.rs
+++ b/src/compiler.rs
@@ -1,6 +1,6 @@
 use std::path::{Path, PathBuf};
 use std::cell::RefCell;
-use std::collections::{HashMap, hash_map::Entry};
+use std::collections::{HashMap, HashSet, hash_map::Entry};
 use std::rc::Rc;
 
 use crate::{Blob, Block, Op, Prog, RustFunction, Type, Value};
@@ -634,10 +634,11 @@ impl Compiler {
             Token::LeftParen => self.grouping_or_tuple(block),
             Token::Minus => self.unary(block),
 
-            Token::Float(_) => self.value(block),
-            Token::Int(_) => self.value(block),
-            Token::Bool(_) => self.value(block),
-            Token::String(_) => self.value(block),
+            Token::Float(_)
+                | Token::Int(_)
+                | Token::Bool(_)
+                | Token::String(_)
+                | Token::Nil => self.value(block),
 
             Token::Bang => self.unary(block),
 
@@ -676,6 +677,7 @@ impl Compiler {
             Token::Float(f) => { Value::Float(f) },
             Token::Int(i) => { Value::Int(i) }
             Token::Bool(b) => { Value::Bool(b) }
+            Token::Nil => { Value::Nil }
             Token::String(s) => { Value::String(Rc::from(s)) }
             _ => { error!(self, "Cannot parse value."); Value::Bool(false) }
         };
@@ -1401,8 +1403,35 @@ impl Compiler {
     }
 
     fn parse_type(&mut self) -> Result<Type, ()> {
-        match self.peek() {
+        let mut tys = HashSet::new();
+        tys.insert(self.parse_simple_type()?);
+        loop {
+            match self.peek() {
+                Token::QuestionMark => {
+                    self.eat();
+                    tys.insert(Type::Void);
+                    return Ok(Type::Union(tys));
+                },
+
+                Token::Pipe => {
+                    self.eat();
+                    tys.insert(self.parse_simple_type()?);
+                },
+
+                _ => {
+                    break;
+                },
+            }
+        }
+        if tys.len() == 1 {
+            Ok(tys.iter().next().unwrap().clone())
+        } else {
+            Ok(Type::Union(tys))
+        }
+    }
 
+    fn parse_simple_type(&mut self) -> Result<Type, ()> {
+        match self.peek() {
             Token::Fn => {
                 self.eat();
                 let mut params = Vec::new();
@@ -1456,6 +1485,7 @@ impl Compiler {
             Token::Identifier(x) => {
                 self.eat();
                 match x.as_str() {
+                    "void" => Ok(Type::Void),
                     "int" => Ok(Type::Int),
                     "float" => Ok(Type::Float),
                     "bool" => Ok(Type::Bool),
@@ -1723,7 +1753,13 @@ impl Compiler {
 
             (Token::Ret, ..) => {
                 self.eat();
-                self.expression(block);
+                if self.peek() == Token::Newline {
+                    self.eat();
+                    let nil = self.add_constant(Value::Nil);
+                    add_op(self, block, Op::Constant(nil));
+                } else {
+                    self.expression(block);
+                }
                 add_op(self, block, Op::Return);
             }
 
diff --git a/src/lib.rs b/src/lib.rs
index a138c33..5ea0b63 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,5 +1,5 @@
 use std::cell::RefCell;
-use std::collections::HashMap;
+use std::collections::{HashMap, HashSet};
 use std::collections::hash_map::Entry;
 use std::fmt::Debug;
 use std::path::{Path, PathBuf};
@@ -86,11 +86,56 @@ pub enum Type {
     Bool,
     String,
     Tuple(Vec<Type>),
+    Union(HashSet<Type>),
     Function(Vec<Type>, Box<Type>),
     Blob(Rc<Blob>),
     Instance(Rc<Blob>),
 }
 
+impl Hash for Type {
+    fn hash<H: Hasher>(&self, h: &mut H) {
+        match self {
+            Type::Void => 0,
+            Type::Unknown => 1,
+            Type::Int => 2,
+            Type::Float => 3,
+            Type::Bool => 4,
+            Type::String => 5,
+            Type::Tuple(ts) => {
+                for t in ts.iter() {
+                    t.hash(h);
+                }
+                6
+            }
+            Type::Union(ts) => {
+                for t in ts {
+                    t.hash(h);
+                }
+                7
+            }
+            Type::Function(args, ret) => {
+                ret.hash(h);
+                for t in args.iter() {
+                    t.hash(h);
+                }
+                8
+            }
+            Type::Blob(b) => {
+                for (_, t) in b.fields.values() {
+                    t.hash(h);
+                }
+                10
+            }
+            Type::Instance(b) => {
+                for (_, t) in b.fields.values() {
+                    t.hash(h);
+                }
+                11
+            }
+        }.hash(h);
+    }
+}
+
 impl PartialEq for Type {
     fn eq(&self, other: &Self) -> bool {
         match (self, other) {
@@ -104,6 +149,9 @@ impl PartialEq for Type {
             (Type::Tuple(a), Type::Tuple(b)) => {
                 a.iter().zip(b.iter()).all(|(a, b)| a == b)
             }
+            (Type::Union(a), b) | (b, Type::Union(a)) => {
+                a.iter().any(|x| x == b)
+            }
             (Type::Function(a_args, a_ret), Type::Function(b_args, b_ret)) =>
                 a_args == b_args && a_ret == b_ret,
             _ => false,
@@ -111,6 +159,8 @@ impl PartialEq for Type {
     }
 }
 
+impl Eq for Type {}
+
 impl From<&Value> for Type {
     fn from(value: &Value) -> Type {
         match value {
@@ -119,6 +169,9 @@ impl From<&Value> for Type {
             Value::Tuple(v) => {
                 Type::Tuple(v.iter().map(|x| Type::from(x)).collect())
             }
+            Value::Union(v) => {
+                Type::Union(v.iter().map(|x| Type::from(x)).collect())
+            }
             Value::Int(_) => Type::Int,
             Value::Float(_) => Type::Float,
             Value::Bool(_) => Type::Bool,
@@ -147,6 +200,9 @@ impl From<&Type> for Value {
             Type::Tuple(fields) => {
                 Value::Tuple(Rc::new(fields.iter().map(Value::from).collect()))
             }
+            Type::Union(v) => {
+                Value::Union(v.iter().map(Value::from).collect())
+            }
             Type::Unknown => Value::Unknown,
             Type::Int => Value::Int(1),
             Type::Float => Value::Float(1.0),
@@ -172,6 +228,7 @@ pub enum Value {
     Blob(Rc<Blob>),
     Instance(Rc<Blob>, Rc<RefCell<Vec<Value>>>),
     Tuple(Rc<Vec<Value>>),
+    Union(HashSet<Value>),
     Float(f64),
     Int(i64),
     Bool(bool),
@@ -200,6 +257,7 @@ impl Debug for Value {
             Value::Unknown => write!(fmt, "(unknown)"),
             Value::Nil => write!(fmt, "(nil)"),
             Value::Tuple(v) => write!(fmt, "({:?})", v),
+            Value::Union(v) => write!(fmt, "(U {:?})", v),
         }
     }
 }
@@ -214,6 +272,9 @@ impl PartialEq<Value> for Value {
             (Value::Tuple(a), Value::Tuple(b)) => {
                 a.len() == b.len() && a.iter().zip(b.iter()).all(|(a, b)| a == b)
             }
+            (Value::Union(a), b) | (b, Value::Union(a)) => {
+                a.iter().any(|x| x == b)
+            }
             (Value::Nil, Value::Nil) => true,
             _ => false,
         }
@@ -566,6 +627,7 @@ pub enum Op {
 mod op {
     use super::{Type, Value};
     use std::rc::Rc;
+    use std::collections::HashSet;
 
     fn tuple_bin_op(a: &Rc<Vec<Value>>, b: &Rc<Vec<Value>>, f: fn (&Value, &Value) -> Value) -> Value {
         Value::Tuple(Rc::new(a.iter().zip(b.iter()).map(|(a, b)| f(a, b)).collect()))
@@ -575,11 +637,34 @@ mod op {
         Value::Tuple(Rc::new(a.iter().map(f).collect()))
     }
 
+    fn union_un_op(a: &HashSet<Value>, f: fn (&Value) -> Value) -> Value {
+        a.iter().find_map(|x| {
+            let x = f(x);
+            if x.is_nil() {
+                None
+            } else {
+                Some(x)
+            }
+        }).unwrap_or(Value::Nil)
+    }
+
+    fn union_bin_op(a: &HashSet<Value>, b: &Value, f: fn (&Value, &Value) -> Value) -> Value {
+        a.iter().find_map(|x| {
+            let x = f(x, b);
+            if x.is_nil() {
+                None
+            } else {
+                Some(x)
+            }
+        }).unwrap_or(Value::Nil)
+    }
+
     pub fn neg(value: &Value) -> Value {
         match value {
             Value::Float(a) => Value::Float(-*a),
             Value::Int(a) => Value::Int(-*a),
             Value::Tuple(a) => tuple_un_op(a, neg),
+            Value::Union(v) => union_un_op(&v, neg),
             Value::Unknown => Value::Unknown,
             _ => Value::Nil,
         }
@@ -589,6 +674,7 @@ mod op {
         match value {
             Value::Bool(a) => Value::Bool(!*a),
             Value::Tuple(a) => tuple_un_op(a, not),
+            Value::Union(v) => union_un_op(&v, not),
             Value::Unknown => Value::from(Type::Bool),
             _ => Value::Nil,
         }
@@ -603,6 +689,7 @@ mod op {
             (Value::Tuple(a), Value::Tuple(b)) if a.len() == b.len() => tuple_bin_op(a, b, add),
             (Value::Unknown, a) | (a, Value::Unknown) if !matches!(a, Value::Unknown) => add(a, a),
             (Value::Unknown, Value::Unknown) => Value::Unknown,
+            (Value::Union(a), b) | (b, Value::Union(a)) => union_bin_op(&a, b, add),
             _ => Value::Nil,
         }
     }
@@ -618,6 +705,7 @@ mod op {
             (Value::Tuple(a), Value::Tuple(b)) if a.len() == b.len() => tuple_bin_op(a, b, mul),
             (Value::Unknown, a) | (a, Value::Unknown) if !matches!(a, Value::Unknown) => mul(a, a),
             (Value::Unknown, Value::Unknown) => Value::Unknown,
+            (Value::Union(a), b) | (b, Value::Union(a)) => union_bin_op(&a, b, mul),
             _ => Value::Nil,
         }
     }
@@ -629,6 +717,7 @@ mod op {
             (Value::Tuple(a), Value::Tuple(b)) if a.len() == b.len() => tuple_bin_op(a, b, div),
             (Value::Unknown, a) | (a, Value::Unknown) if !matches!(a, Value::Unknown) => div(a, a),
             (Value::Unknown, Value::Unknown) => Value::Unknown,
+            (Value::Union(a), b) | (b, Value::Union(a)) => union_bin_op(&a, b, div),
             _ => Value::Nil,
         }
     }
@@ -639,9 +728,17 @@ mod op {
             (Value::Int(a), Value::Int(b)) => Value::Bool(a == b),
             (Value::String(a), Value::String(b)) => Value::Bool(a == b),
             (Value::Bool(a), Value::Bool(b)) => Value::Bool(a == b),
-            (Value::Tuple(a), Value::Tuple(b)) if a.len() == b.len() => tuple_bin_op(a, b, eq),
+            (Value::Tuple(a), Value::Tuple(b)) if a.len() == b.len() => {
+                a.iter().zip(b.iter()).find_map(
+                    |(a, b)| match eq(a, b) {
+                        Value::Bool(true) => None,
+                        a => Some(a),
+                    }).unwrap_or(Value::Bool(true))
+            }
             (Value::Unknown, a) | (a, Value::Unknown) if !matches!(a, Value::Unknown) => eq(a, a),
             (Value::Unknown, Value::Unknown) => Value::Unknown,
+            (Value::Union(a), b) | (b, Value::Union(a)) => union_bin_op(&a, b, eq),
+            (Value::Nil, Value::Nil) => Value::Bool(true),
             _ => Value::Nil,
         }
     }
@@ -652,9 +749,16 @@ mod op {
             (Value::Int(a), Value::Int(b)) => Value::Bool(a < b),
             (Value::String(a), Value::String(b)) => Value::Bool(a < b),
             (Value::Bool(a), Value::Bool(b)) => Value::Bool(a < b),
-            (Value::Tuple(a), Value::Tuple(b)) if a.len() == b.len() => tuple_bin_op(a, b, less),
+            (Value::Tuple(a), Value::Tuple(b)) if a.len() == b.len() => {
+                a.iter().zip(b.iter()).find_map(
+                    |(a, b)| match less(a, b) {
+                        Value::Bool(true) => None,
+                        a => Some(a),
+                    }).unwrap_or(Value::Bool(true))
+            }
             (Value::Unknown, a) | (a, Value::Unknown) if !matches!(a, Value::Unknown) => less(a, a),
             (Value::Unknown, Value::Unknown) => Value::Unknown,
+            (Value::Union(a), b) | (b, Value::Union(a)) => union_bin_op(&a, b, less),
             _ => Value::Nil,
         }
     }
@@ -669,6 +773,7 @@ mod op {
             (Value::Tuple(a), Value::Tuple(b)) if a.len() == b.len() => tuple_bin_op(a, b, and),
             (Value::Unknown, a) | (a, Value::Unknown) if !matches!(a, Value::Unknown) => and(a, a),
             (Value::Unknown, Value::Unknown) => Value::Unknown,
+            (Value::Union(a), b) | (b, Value::Union(a)) => union_bin_op(&a, b, and),
             _ => Value::Nil,
         }
     }
@@ -679,6 +784,7 @@ mod op {
             (Value::Tuple(a), Value::Tuple(b)) if a.len() == b.len() => tuple_bin_op(a, b, or),
             (Value::Unknown, a) | (a, Value::Unknown) if !matches!(a, Value::Unknown) => or(a, a),
             (Value::Unknown, Value::Unknown) => Value::Unknown,
+            (Value::Union(a), b) | (b, Value::Union(a)) => union_bin_op(&a, b, or),
             _ => Value::Nil,
         }
     }
diff --git a/src/tokenizer.rs b/src/tokenizer.rs
index 3b61e5f..8b06324 100644
--- a/src/tokenizer.rs
+++ b/src/tokenizer.rs
@@ -15,6 +15,9 @@ pub enum Token {
     #[regex(r"[\d]+", |lex| lex.slice().parse())]
     Int(i64),
 
+    #[regex(r"nil")]
+    Nil,
+
     #[regex(r"true|false", |lex| lex.slice().parse(), priority=2)]
     Bool(bool),
 
@@ -117,6 +120,10 @@ pub enum Token {
     Or,
     #[token("!")]
     Bang,
+    #[token("?")]
+    QuestionMark,
+    #[token("|")]
+    Pipe,
 
     #[token(",")]
     Comma,
diff --git a/src/vm.rs b/src/vm.rs
index e001ebc..3652321 100644
--- a/src/vm.rs
+++ b/src/vm.rs
@@ -1,6 +1,6 @@
 use std::cell::RefCell;
 use std::collections::hash_map::Entry;
-use std::collections::HashMap;
+use std::collections::{HashMap, HashSet};
 use std::fmt::Debug;
 use std::rc::Rc;
 
@@ -656,7 +656,7 @@ impl VM {
                 let ret = inner.ret();
                 if Type::from(&a) != *ret {
 
-                    error!(self, ErrorKind::TypeMismatch(a.into(), ret.clone()),
+                    error!(self, ErrorKind::TypeMismatch(ret.clone(), a.into()),
                            "Value does not match return type.");
                 }
             }
@@ -669,6 +669,10 @@ impl VM {
                 let ty = self.ty(ty);
                 let top_type = self.stack.last().unwrap().into();
                 match (ty, top_type) {
+                    (a, b) if matches!(a, Type::Union(_)) && a == &b => {
+                        let last = self.stack.len() - 1;
+                        self.stack[last] = Value::from(a);
+                    }
                     (Type::Unknown, top_type)
                         if top_type != Type::Unknown => {}
                     (a, b) if a != &b => {
@@ -725,55 +729,76 @@ impl VM {
 
             Op::Call(num_args) => {
                 let new_base = self.stack.len() - 1 - num_args;
-                match self.stack[new_base].clone() {
-                    Value::Blob(blob) => {
-                        let mut values = Vec::with_capacity(blob.fields.len());
-                        for _ in 0..values.capacity() {
-                            values.push(Value::Nil);
-                        }
+                let callable = &self.stack[new_base];
+
+                let call_callable = |callable: &Value| {
+                    let args = &self.stack[new_base+1..];
+                    let args: Vec<_> = args.iter().map(|x| x.into()).collect();
+                    match callable {
+                        Value::Blob(blob) => {
+                            let mut values = Vec::with_capacity(blob.fields.len());
+                            for _ in 0..values.capacity() {
+                                values.push(Value::Nil);
+                            }
 
-                        for (slot, ty) in blob.fields.values() {
-                            values[*slot] = ty.into();
-                        }
+                            for (slot, ty) in blob.fields.values() {
+                                values[*slot] = ty.into();
+                            }
 
-                        self.pop();
-                        self.push(Value::Instance(blob, Rc::new(RefCell::new(values))));
-                    }
-                    Value::Function(_, block) => {
-                        let inner = block.borrow();
-                        let args = inner.args();
-                        if args.len() != num_args {
-                            error!(self, ErrorKind::ArgumentCount(args.len(), num_args));
+                            Ok(Value::Instance(blob.clone(), Rc::new(RefCell::new(values))))
                         }
 
-                        let stack_args = &self.stack[self.stack.len() - args.len()..];
-                        let stack_args: Vec<_> = stack_args.iter().map(|x| x.into()).collect();
-                        if args != &stack_args {
-                            error!(self, ErrorKind::ArgumentType(args.clone(), stack_args));
+                        Value::Function(_, block) => {
+                            let inner = block.borrow();
+                            let fargs = inner.args();
+                            if fargs != &args {
+                                Err(ErrorKind::ArgumentType(args.clone(), args))
+                            } else {
+                                Ok(inner.ret().into())
+                            }
+
                         }
 
-                        self.stack[new_base] = block.borrow().ret().into();
+                        Value::ExternFunction(slot) => {
+                            let extern_func = self.extern_functions[*slot];
+                            extern_func(&self.stack[new_base+1..], false)
+                        }
 
-                        self.stack.truncate(new_base + 1);
+                        _ => {
+                            Err(ErrorKind::InvalidProgram)
+                        }
                     }
-                    Value::ExternFunction(slot) => {
-                        let extern_func = self.extern_functions[slot];
-                        let res = match extern_func(&self.stack[new_base+1..], false) {
-                            Ok(value) => value,
-                            Err(ek) => {
-                                self.stack.truncate(new_base);
-                                self.push(Value::Nil);
-                                error!(self, ek, "Error from external function.")
+                };
+
+                let mut err = None;
+                self.stack[new_base] = match callable {
+                    Value::Union(alts) => {
+                        let mut returns = HashSet::new();
+                        for alt in alts.iter() {
+                            if let Ok(res) = call_callable(&alt) {
+                                returns.insert(res);
                             }
-                        };
-                        self.stack.truncate(new_base);
-                        self.push(res);
-                    }
+                        }
+                        if returns.is_empty() {
+                            err = Some(ErrorKind::InvalidProgram);
+                            Value::Nil
+                        } else {
+                            Value::Union(returns)
+                        }
+                    },
                     _ => {
-                        error!(self,
-                            ErrorKind::InvalidProgram,
-                            format!("Tried to call non-function {:?}", self.stack[new_base]));
+                        match call_callable(callable) {
+                            Err(e) => {
+                                err = Some(e);
+                                Value::Nil
+                            },
+                            Ok(v) => v
+                        }
                     }
+                };
+                self.stack.truncate(new_base + 1);
+                if err.is_some() {
+                    error!(self, err.unwrap());
                 }
             }