Add the start of a hindley-milner typechecker

The beginning of a parse-don't-validate-based hindley-milner
typechecker, which returns on success an IR where every AST node
trivially knows its own type, and using those types to determine LLVM
types in codegen.

2 files changed, 27 insertions, 8 deletions

diff --git a/src/common/env.rs b/src/common/env.rs
index f499323639e3..59a5e46c466f 100644
--- a/src/common/env.rs
+++ b/src/common/env.rs
@@ -1,19 +1,25 @@
+use std::borrow::Borrow;
 use std::collections::HashMap;
+use std::hash::Hash;
 use std::mem;
 
-use crate::ast::Ident;
-
 /// A lexical environment
 #[derive(Debug, PartialEq, Eq)]
-pub struct Env<'ast, V>(Vec<HashMap<&'ast Ident<'ast>, V>>);
+pub struct Env<K: Eq + Hash, V>(Vec<HashMap<K, V>>);
 
-impl<'ast, V> Default for Env<'ast, V> {
+impl<K, V> Default for Env<K, V>
+where
+    K: Eq + Hash,
+{
     fn default() -> Self {
         Self::new()
     }
 }
 
-impl<'ast, V> Env<'ast, V> {
+impl<K, V> Env<K, V>
+where
+    K: Eq + Hash,
+{
     pub fn new() -> Self {
         Self(vec![Default::default()])
     }
@@ -34,11 +40,15 @@ impl<'ast, V> Env<'ast, V> {
         *self = saved;
     }
 
-    pub fn set(&mut self, k: &'ast Ident<'ast>, v: V) {
+    pub fn set(&mut self, k: K, v: V) {
         self.0.last_mut().unwrap().insert(k, v);
     }
 
-    pub fn resolve<'a>(&'a self, k: &'ast Ident<'ast>) -> Option<&'a V> {
+    pub fn resolve<'a, Q>(&'a self, k: &Q) -> Option<&'a V>
+    where
+        K: Borrow<Q>,
+        Q: Hash + Eq + ?Sized,
+    {
         for ctx in self.0.iter().rev() {
             if let Some(res) = ctx.get(k) {
                 return Some(res);
diff --git a/src/common/error.rs b/src/common/error.rs
index f3f3023ceaf8..51575a895e91 100644
--- a/src/common/error.rs
+++ b/src/common/error.rs
@@ -2,7 +2,7 @@ use std::{io, result};
 
 use thiserror::Error;
 
-use crate::{codegen, interpreter, parser};
+use crate::{codegen, interpreter, parser, tc};
 
 #[derive(Error, Debug)]
 pub enum Error {
@@ -18,6 +18,9 @@ pub enum Error {
     #[error("Compile error: {0}")]
     CodegenError(#[from] codegen::Error),
 
+    #[error("Type error: {0}")]
+    TypeError(#[from] tc::Error),
+
     #[error("{0}")]
     Message(String),
 }
@@ -28,6 +31,12 @@ impl From<String> for Error {
     }
 }
 
+impl<'a> From<&'a str> for Error {
+    fn from(s: &'a str) -> Self {
+        Self::Message(s.to_owned())
+    }
+}
+
 impl<'a> From<nom::Err<nom::error::Error<&'a str>>> for Error {
     fn from(e: nom::Err<nom::error::Error<&'a str>>) -> Self {
         use nom::error::Error as NomError;