Repository: gluon-lang/gluon
Pull request #710 (2019-04-10 21:52:55)

fix(check): Bring nested implicit instances into scope
Traverses records fully to bring their implicit instances in scope (`Monad -> Applicative -> Functor` etc)

Found in #686

cc @Etherian


Patch:
diff --git a/.travis.yml b/.travis.yml
index 914ee6bb..b5013379 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -110,6 +110,13 @@ before_deploy:
 before_cache:
     - rm -rf /home/travis/.cargo/registry
 deploy:
+  - provider: pages
+    skip-cleanup: true
+    github-token: $GITHUB_TOKEN
+    local-dir: book/book
+    on:
+        branch: master
+
   - provider: releases
     api_key:
       secure: ImhF+DkxyHyzDQ4SZZlATjgkrzr+yY1xwADxgO2B5Xi+C7AOllkPInSB/RL+C6tebQnxIEop7KU0N4svbIw6zuoDmOvkliP++U1gXDqvpggBT7AXM5ICcLKWUzTdh3XexhL5SUmtH+QvWRwFwcOoq6mic8rc6DSvTojB/NydyJCeHGvx5iSl5o/ZSqrnEjOF/yDMXADVNwQRZebzyXss+wtTfEbD7OZoJ9ihPugDES8EkmScwS/UCJfCfEqBf/AwDSaAxVpPB/2PF7J0bDIB1ORrwA4HUguJ/U5QuV4vea0hNhhIzzwfcsbPhPLARcLENZLirUk3iygbwSPCTNg+8yEz0MPJQVTj/T48cbKkn9rgZfWi3Bs9nyv22ZouKBFQooiQD6b7WhVGY8bA1Q39cTSLfrR9WrkiRS3x11QrNkwWUqvWHb+2u0KtovTnCt9Lxrx0j8WKMO5Onx6hLfGfH00puCNpV8keWqkzriSi7/ce4mBl8HTvFX22bKZ5uZAxX2mPodAtWoh8hgOGMZhjG2ODS1CEQBxWw5nCXkKQE1afaJOEjhzXmmSNzTnfWIFQGk6V9T9LF8u/PrSVmkQCgka/arlUQlKl+Fa8XUEx8DZEHptj2OdP86A2qiUOcsAmYF2z19kYziHYK3Ll1xDPoOSil6Eej5t+n/e37bmvTMY=
diff --git a/base/src/types/mod.rs b/base/src/types/mod.rs
index 4ee2d3ee..ca6f847c 100644
--- a/base/src/types/mod.rs
+++ b/base/src/types/mod.rs
@@ -74,7 +74,7 @@ macro_rules! forward_eq_hash {
 pub trait TypeEnv: KindEnv {
     type Type;
     /// Returns the type of the value bound at `id`
-    fn find_type(&self, id: &SymbolRef) -> Option<&Self::Type>;
+    fn find_type(&self, id: &SymbolRef) -> Option<ModType<&Self::Type>>;
 
     /// Returns information about the type `id`
     fn find_type_info(&self, id: &SymbolRef) -> Option<&Alias<Symbol, Self::Type>>;
@@ -83,7 +83,7 @@ pub trait TypeEnv: KindEnv {
 impl<'a, T: ?Sized + TypeEnv> TypeEnv for &'a T {
     type Type = T::Type;
 
-    fn find_type(&self, id: &SymbolRef) -> Option<&Self::Type> {
+    fn find_type(&self, id: &SymbolRef) -> Option<ModType<&Self::Type>> {
         (**self).find_type(id)
     }
 
@@ -95,7 +95,7 @@ impl<'a, T: ?Sized + TypeEnv> TypeEnv for &'a T {
 impl TypeEnv for EmptyEnv<Symbol> {
     type Type = ArcType;
 
-    fn find_type(&self, _id: &SymbolRef) -> Option<&ArcType> {
+    fn find_type(&self, _id: &SymbolRef) -> Option<ModType<&ArcType>> {
         None
     }
 
@@ -3759,3 +3759,100 @@ where
         Type::EmptyRow => interner.empty_row(),
     }
 }
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum TypeModifier {
+    Wobbly,
+    Rigid,
+}
+
+impl Default for TypeModifier {
+    fn default() -> Self {
+        TypeModifier::Wobbly
+    }
+}
+
+impl ops::BitOr for TypeModifier {
+    type Output = Self;
+
+    fn bitor(mut self, typ: Self) -> Self {
+        self |= typ;
+        self
+    }
+}
+impl ops::BitOrAssign for TypeModifier {
+    fn bitor_assign(&mut self, typ: Self) {
+        match (*self, typ) {
+            (TypeModifier::Rigid, TypeModifier::Rigid) => (),
+            _ => *self = TypeModifier::Wobbly,
+        }
+    }
+}
+
+pub type ModTypeRef<'a> = ModType<&'a ArcType>;
+
+#[derive(Clone, Copy, Debug)]
+pub struct ModType<T = ArcType> {
+    pub modifier: TypeModifier,
+    pub concrete: T,
+}
+
+impl<T> fmt::Display for ModType<T>
+where
+    T: fmt::Display,
+{
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        self.concrete.fmt(f)
+    }
+}
+
+impl<T> Deref for ModType<T> {
+    type Target = T;
+
+    fn deref(&self) -> &Self::Target {
+        &self.concrete
+    }
+}
+
+impl<T> DerefMut for ModType<T> {
+    fn deref_mut(&mut self) -> &mut Self::Target {
+        &mut self.concrete
+    }
+}
+
+impl<T> ops::BitOrAssign for ModType<T> {
+    fn bitor_assign(&mut self, typ: Self) {
+        self.modifier |= typ.modifier;
+        self.concrete = typ.concrete;
+    }
+}
+
+impl<T> ModType<T> {
+    pub fn new(modifier: TypeModifier, typ: T) -> Self {
+        ModType {
+            modifier,
+            concrete: typ,
+        }
+    }
+
+    pub fn rigid(typ: T) -> Self {
+        Self::new(TypeModifier::Rigid, typ)
+    }
+
+    pub fn wobbly(typ: T) -> Self {
+        Self::new(TypeModifier::Wobbly, typ)
+    }
+
+    pub fn as_ref(&self) -> ModType<&T> {
+        ModType::new(self.modifier, &self.concrete)
+    }
+}
+
+impl<'a, T> ModType<&'a T>
+where
+    T: Clone,
+{
+    pub fn to_owned(&self) -> ModType<T> {
+        ModType::new(self.modifier, self.concrete.clone())
+    }
+}
diff --git a/check/src/implicits.rs b/check/src/implicits.rs
index 51e523f0..7a46d65b 100644
--- a/check/src/implicits.rs
+++ b/check/src/implicits.rs
@@ -22,7 +22,7 @@ use crate::base::{
     resolve,
     scoped_map::{self, ScopedMap},
     symbol::{Symbol, SymbolRef},
-    types::{self, ArgType, BuiltinType, Type, TypeExt},
+    types::{self, ArgType, BuiltinType, Type, TypeContext, TypeExt},
 };
 
 use crate::{
@@ -142,6 +142,33 @@ where
     }
 }
 
+impl fmt::Display for Partition<ImplicitBinding> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_struct("Partition")
+            .field(
+                "partition",
+                &format_args!(
+                    "[{}]",
+                    self.partition
+                        .iter()
+                        .format_with(",", |i, f| f(&format_args!("{}", i.1)))
+                ),
+            )
+            .field(
+                "rest",
+                &format_args!(
+                    "[{}]",
+                    self.rest.iter().format_with(",", |i, f| f(&format_args!(
+                        "{}: {}",
+                        i.0.iter().map(|i| &i.name).format("."),
+                        i.1
+                    )))
+                ),
+            )
+            .finish()
+    }
+}
+
 impl<T> Clone for Partition<T> {
     fn clone(&self) -> Self {
         Partition {
@@ -245,7 +272,9 @@ impl Partition<ImplicitBinding> {
                 let opt = {
                     let bind = vec.get(i).unwrap();
                     if bind.0.len() == 1 {
-                        let typ = f(&bind.0[0].name).unwrap();
+                        let name = &bind.0[0].name;
+                        let typ =
+                            f(name).unwrap_or_else(|| ice!("Unable to update implicit `{}`", name));
                         Some((bind.0.clone(), typ))
                     } else {
                         None
@@ -280,6 +309,12 @@ pub(crate) struct ImplicitBindings {
     pub definitions: ::rpds::HashTrieSet<Symbol>,
 }
 
+impl fmt::Display for ImplicitBindings {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        write!(f, "{}", self.partition)
+    }
+}
+
 impl ImplicitBindings {
     fn new() -> ImplicitBindings {
         ImplicitBindings::default()
@@ -745,9 +780,17 @@ impl<'a> ImplicitResolver<'a> {
         if self.implicit_bindings.is_empty() {
             self.implicit_bindings.push(ImplicitBindings::new());
         }
+
         let metadata = self.metadata.get(id);
 
-        let opt = self.try_create_implicit(&id, metadata.map(|m| &**m), &typ, &mut Vec::new());
+        let opt = self.try_create_implicit(
+            metadata.map(|m| &**m),
+            &typ,
+            &[TypedIdent {
+                name: id.clone(),
+                typ: typ.clone(),
+            }],
+        );
 
         if let Some((definition, path, implicit_type)) = opt {
             self.implicit_bindings.last_mut().unwrap().insert(
@@ -761,20 +804,39 @@ impl<'a> ImplicitResolver<'a> {
 
     pub fn add_implicits_of_record(
         &mut self,
-        mut subs: &Substitution<RcType>,
+        subs: &Substitution<RcType>,
         id: &Symbol,
         typ: &RcType,
     ) {
-        info!("Trying to resolve implicit {}", typ);
-
         if self.implicit_bindings.is_empty() {
             self.implicit_bindings.push(ImplicitBindings::new());
         }
 
+        let mut path = Vec::new();
+        path.push(TypedIdent {
+            name: id.clone(),
+            typ: typ.clone(),
+        });
+
+        let meta = self.metadata.get(id).cloned();
+        self.add_implicits_of_record_rec(subs, typ, meta.as_ref().map(|m| &**m), &mut path);
+    }
+
+    fn add_implicits_of_record_rec(
+        &mut self,
+        mut subs: &Substitution<RcType>,
+        typ: &RcType,
+        metadata: Option<&Metadata>,
+        path: &mut Vec<TypedIdent<Symbol, RcType>>,
+    ) {
         let mut alias_resolver = resolve::AliasRemover::new();
 
-        let typ = subs.real(typ).clone();
-        let ref typ = typ.instantiate_generics(&mut subs, &mut FnvMap::default());
+        let mut typ = subs.real(typ).clone();
+        let mut forall_params = Vec::new();
+        while let Type::Forall(params, next) = &*typ {
+            forall_params.extend(params.iter().cloned());
+            typ = next.clone();
+        }
         let raw_type =
             match alias_resolver.remove_aliases(&self.environment, &mut subs, typ.clone()) {
                 Ok(t) => t,
@@ -783,24 +845,20 @@ impl<'a> ImplicitResolver<'a> {
             };
         match *raw_type {
             Type::Record(_) => {
-                let metadata = self.metadata.get(id);
-
-                let mut path = vec![TypedIdent {
-                    name: id.clone(),
-                    typ: typ.clone(),
-                }];
-
                 for field in raw_type.row_iter() {
                     let field_metadata = metadata
-                        .as_ref()
-                        .and_then(|metadata| metadata.module.get(field.name.as_pretty_str()));
+                        .and_then(|metadata| metadata.module.get(field.name.as_pretty_str()))
+                        .map(|m| &**m);
 
-                    let opt = self.try_create_implicit(
-                        &field.name,
-                        field_metadata.map(|m| &**m),
-                        &field.typ,
-                        &mut path,
-                    );
+                    let field_type =
+                        subs.forall(forall_params.iter().cloned().collect(), field.typ.clone());
+
+                    path.push(TypedIdent {
+                        name: field.name.clone(),
+                        typ: field_type.clone(),
+                    });
+
+                    let opt = self.try_create_implicit(field_metadata, &field_type, path);
 
                     if let Some((definition, path, implicit_type)) = opt {
                         self.implicit_bindings.last_mut().unwrap().insert(
@@ -810,6 +868,10 @@ impl<'a> ImplicitResolver<'a> {
                             &implicit_type,
                         );
                     }
+
+                    self.add_implicits_of_record_rec(subs, &field.typ, field_metadata, path);
+
+                    path.pop();
                 }
             }
             _ => (),
@@ -818,10 +880,9 @@ impl<'a> ImplicitResolver<'a> {
 
     pub fn try_create_implicit<'m>(
         &self,
-        id: &Symbol,
         metadata: Option<&'m Metadata>,
         typ: &RcType,
-        path: &mut Vec<TypedIdent<Symbol, RcType>>,
+        path: &[TypedIdent<Symbol, RcType>],
     ) -> Option<(Option<&'m Symbol>, Vec<TypedIdent<Symbol, RcType>>, RcType)> {
         let has_implicit_attribute =
             |metadata: &Metadata| metadata.get_attribute("implicit").is_some();
@@ -861,11 +922,7 @@ impl<'a> ImplicitResolver<'a> {
                 }
             }
 
-            let mut path = path.clone();
-            path.push(TypedIdent {
-                name: id.clone(),
-                typ: typ.clone(),
-            });
+            let path = path.to_owned();
             Some((
                 metadata.and_then(|m| m.definition.as_ref()),
                 path,
diff --git a/check/src/lib.rs b/check/src/lib.rs
index 5d65edfd..5b128616 100644
--- a/check/src/lib.rs
+++ b/check/src/lib.rs
@@ -89,7 +89,7 @@ mod tests {
     use crate::base::{
         kind::{ArcKind, KindEnv},
         symbol::{Symbol, SymbolModule, SymbolRef, Symbols},
-        types::{Alias, TypeEnv},
+        types::{Alias, ModTypeRef, TypeEnv},
     };
 
     pub struct MockEnv;
@@ -102,7 +102,7 @@ mod tests {
 
     impl TypeEnv for MockEnv {
         type Type = RcType;
-        fn find_type(&self, _id: &SymbolRef) -> Option<&ArcType> {
+        fn find_type(&self, _id: &SymbolRef) -> Option<ModTypeRef> {
             None
         }
         fn find_type_info(&self, _id: &SymbolRef) -> Option<&Alias<Symbol, RcType>> {
diff --git a/check/src/typecheck.rs b/check/src/typecheck.rs
index daf756a7..941c78d2 100644
--- a/check/src/typecheck.rs
+++ b/check/src/typecheck.rs
@@ -25,8 +25,8 @@ use crate::base::{
     scoped_map::{self, ScopedMap},
     symbol::{Symbol, SymbolModule, SymbolRef, Symbols},
     types::{
-        self, Alias, AliasRef, AppVec, ArcType, ArgType, Field, Flags, Generic, PrimitiveEnv, Type,
-        TypeCache, TypeContext, TypeEnv, TypeExt,
+        self, Alias, AliasRef, AppVec, ArcType, ArgType, Field, Flags, Generic, ModType,
+        ModTypeRef, PrimitiveEnv, Type, TypeCache, TypeContext, TypeEnv, TypeExt, TypeModifier,
     },
 };
 
@@ -38,16 +38,12 @@ use crate::{
     unify, unify_type, TypecheckEnv,
 };
 
-use self::{
-    generalize::TypeGeneralizer,
-    mod_type::{ModType, ModTypeRef, TypeModifier},
-};
+use self::generalize::TypeGeneralizer;
 
 pub use self::error::{Help, HelpError, SpannedTypeError, TypeError};
 
 mod error;
 mod generalize;
-mod mod_type;
 
 pub(crate) type TcResult<T> = Result<T, TypeError<Symbol, RcType<Symbol>>>;
 
@@ -90,10 +86,10 @@ impl<'a> KindEnv for Environment<'a> {
 impl<'a> TypeEnv for Environment<'a> {
     type Type = RcType;
 
-    fn find_type(&self, id: &SymbolRef) -> Option<&ArcType> {
+    fn find_type(&self, id: &SymbolRef) -> Option<ModTypeRef> {
         self.stack
             .get(id)
-            .map(|bind| &bind.typ.concrete)
+            .map(|bind| bind.typ.as_ref())
             .or_else(|| self.environment.find_type(id))
     }
 
@@ -117,15 +113,6 @@ impl<'a> MetadataEnv for Environment<'a> {
     }
 }
 
-impl Environment<'_> {
-    fn find_mod_type(&self, id: &SymbolRef) -> Option<ModTypeRef> {
-        self.stack
-            .get(id)
-            .map(|bind| bind.typ.as_ref())
-            .or_else(|| self.environment.find_type(id).map(ModType::rigid))
-    }
-}
-
 /// Type returned from the main typecheck function to make sure that nested `type` and `let`
 /// expressions dont overflow the stack
 enum TailCall {
@@ -217,7 +204,7 @@ impl<'a> Typecheck<'a> {
     }
 
     fn find(&mut self, id: &Symbol) -> TcResult<ModType> {
-        match self.environment.find_mod_type(id).map(|t| t.to_owned()) {
+        match self.environment.find_type(id).map(|t| t.to_owned()) {
             Some(typ) => {
                 self.named_variables.clear();
                 debug!("Find {} : {}", self.symbols.string(id), typ);
@@ -2025,13 +2012,20 @@ impl<'a> Typecheck<'a> {
             }
 
             debug!("End generalize recursive");
-
-            // Update the implicit bindings with the generalized types we just created
-            let bindings = self.implicit_resolver.implicit_bindings.last_mut().unwrap();
-
-            let stack = &self.environment.stack;
-            bindings.update(|name| Some(stack.get(name).unwrap().typ.concrete.clone()));
         }
+        // Update the implicit bindings with the generalized types we just created
+        let bindings = self.implicit_resolver.implicit_bindings.last_mut().unwrap();
+        let stack = &self.environment.stack;
+        bindings.update(|name| {
+            Some(
+                stack
+                    .get(name)
+                    .unwrap_or_else(|| ice!("Implicit binding `{}` could not be updated", name))
+                    .typ
+                    .concrete
+                    .clone(),
+            )
+        });
 
         debug!("Typecheck `in`");
         self.environment.type_variables.exit_scope();
@@ -3156,7 +3150,7 @@ pub fn translate_projected_type(
             }
             None => Some(
                 env.find_type(&symbol)
-                    .cloned()
+                    .map(|t| t.concrete.clone())
                     .or_else(|| {
                         env.find_type_info(&symbol)
                             .map(|alias| alias.typ(interner).into_owned())
diff --git a/check/src/typecheck/mod_type.rs b/check/src/typecheck/mod_type.rs
deleted file mode 100644
index aa9b5e4a..00000000
--- a/check/src/typecheck/mod_type.rs
+++ /dev/null
@@ -1,100 +0,0 @@
-use std::{fmt, ops};
-
-use base::types::ArcType;
-
-#[derive(Clone, Copy, Debug, Eq, PartialEq)]
-pub enum TypeModifier {
-    Wobbly,
-    Rigid,
-}
-
-impl Default for TypeModifier {
-    fn default() -> Self {
-        TypeModifier::Wobbly
-    }
-}
-
-impl ops::BitOr for TypeModifier {
-    type Output = Self;
-
-    fn bitor(mut self, typ: Self) -> Self {
-        self |= typ;
-        self
-    }
-}
-impl ops::BitOrAssign for TypeModifier {
-    fn bitor_assign(&mut self, typ: Self) {
-        match (*self, typ) {
-            (TypeModifier::Rigid, TypeModifier::Rigid) => (),
-            _ => *self = TypeModifier::Wobbly,
-        }
-    }
-}
-
-pub type ModTypeRef<'a> = ModType<&'a ArcType>;
-
-#[derive(Clone, Copy, Debug)]
-pub struct ModType<T = ArcType> {
-    pub modifier: TypeModifier,
-    pub concrete: T,
-}
-
-impl<T> fmt::Display for ModType<T>
-where
-    T: fmt::Display,
-{
-    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
-        self.concrete.fmt(f)
-    }
-}
-
-impl<T> ops::Deref for ModType<T> {
-    type Target = T;
-
-    fn deref(&self) -> &Self::Target {
-        &self.concrete
-    }
-}
-
-impl<T> ops::DerefMut for ModType<T> {
-    fn deref_mut(&mut self) -> &mut Self::Target {
-        &mut self.concrete
-    }
-}
-
-impl<T> ops::BitOrAssign for ModType<T> {
-    fn bitor_assign(&mut self, typ: Self) {
-        self.modifier |= typ.modifier;
-        self.concrete = typ.concrete;
-    }
-}
-
-impl<T> ModType<T> {
-    pub fn new(modifier: TypeModifier, typ: T) -> Self {
-        ModType {
-            modifier,
-            concrete: typ,
-        }
-    }
-
-    pub fn rigid(typ: T) -> Self {
-        Self::new(TypeModifier::Rigid, typ)
-    }
-
-    pub fn wobbly(typ: T) -> Self {
-        Self::new(TypeModifier::Wobbly, typ)
-    }
-
-    pub fn as_ref(&self) -> ModType<&T> {
-        ModType::new(self.modifier, &self.concrete)
-    }
-}
-
-impl<'a, T> ModType<&'a T>
-where
-    T: Clone,
-{
-    pub fn to_owned(&self) -> ModType<T> {
-        ModType::new(self.modifier, self.concrete.clone())
-    }
-}
diff --git a/completion/src/lib.rs b/completion/src/lib.rs
index 0f24945d..c7a94ba4 100644
--- a/completion/src/lib.rs
+++ b/completion/src/lib.rs
@@ -1471,7 +1471,7 @@ impl SuggestionQuery {
                         name,
                         typ: Either::Right(
                             env.find_type(SymbolRef::new(module))
-                                .cloned()
+                                .map(|t| t.concrete.clone())
                                 .unwrap_or_else(Type::hole),
                         ),
                     }
diff --git a/examples/http/main.rs b/examples/http/main.rs
index c7c0d472..937a754c 100644
--- a/examples/http/main.rs
+++ b/examples/http/main.rs
@@ -97,6 +97,8 @@ mod tests {
 
     #[test]
     fn hello_world() {
+        let _ = env_logger::try_init();
+
         let mut runtime = Runtime::new().unwrap();
 
         let port = 12234;
@@ -115,6 +117,8 @@ mod tests {
 
     #[test]
     fn echo() {
+        let _ = env_logger::try_init();
+
         let mut runtime = Runtime::new().unwrap();
 
         let port = 12235;
diff --git a/std/list.glu b/std/list.glu
index 130fb784..31734ecd 100644
--- a/std/list.glu
+++ b/std/list.glu
@@ -97,7 +97,6 @@ let many ?alt x : [Alternative f] -> f a -> f (List a) =
     let many_v _ =
         some_v () <|> wrap Nil
     let some_v _ =
-        let { ? } = alt.applicative
         map (\h l -> Cons h l) x <*> many_v ()
     in
     many_v ()
@@ -108,7 +107,6 @@ let some ?alt x : [Alternative f] -> f a -> f (List a) =
     let many_v _ =
         some_v () <|> wrap Nil
     let some_v _ =
-        let { ? } = alt.applicative
         map (\h l -> Cons h l) x <*> many_v ()
     in
     some_v ()
diff --git a/vm/src/compiler.rs b/vm/src/compiler.rs
index c6709d2c..360b4863 100644
--- a/vm/src/compiler.rs
+++ b/vm/src/compiler.rs
@@ -8,7 +8,7 @@ use crate::base::{
     scoped_map::ScopedMap,
     source::Source,
     symbol::{Symbol, SymbolModule, SymbolRef},
-    types::{Alias, ArcType, BuiltinType, NullInterner, Type, TypeEnv, TypeExt},
+    types::{Alias, ArcType, BuiltinType, ModTypeRef, NullInterner, Type, TypeEnv, TypeExt},
 };
 
 use crate::{
@@ -451,7 +451,7 @@ impl<'a> KindEnv for Compiler<'a> {
 impl<'a> TypeEnv for Compiler<'a> {
     type Type = ArcType;
 
-    fn find_type(&self, _id: &SymbolRef) -> Option<&ArcType> {
+    fn find_type(&self, _id: &SymbolRef) -> Option<ModTypeRef> {
         None
     }
 
diff --git a/vm/src/core/interpreter.rs b/vm/src/core/interpreter.rs
index cf828148..748bc510 100644
--- a/vm/src/core/interpreter.rs
+++ b/vm/src/core/interpreter.rs
@@ -7,7 +7,7 @@ use crate::base::{
     merge::merge_iter,
     scoped_map::ScopedMap,
     symbol::{Symbol, SymbolRef},
-    types::{Alias, ArcType, TypeEnv, TypeExt},
+    types::{Alias, ArcType, ModTypeRef, TypeEnv, TypeExt},
 };
 
 use crate::{
@@ -293,7 +293,7 @@ impl<'a, 'e> KindEnv for Compiler<'a, 'e> {
 impl<'a, 'e> TypeEnv for Compiler<'a, 'e> {
     type Type = ArcType;
 
-    fn find_type(&self, _id: &SymbolRef) -> Option<&ArcType> {
+    fn find_type(&self, _id: &SymbolRef) -> Option<ModTypeRef> {
         None
     }
 
diff --git a/vm/src/types.rs b/vm/src/types.rs
index 45131389..e9d1e6fb 100644
--- a/vm/src/types.rs
+++ b/vm/src/types.rs
@@ -2,7 +2,7 @@ use crate::base::{
     fnv::FnvMap,
     kind::{ArcKind, Kind, KindEnv},
     symbol::{Symbol, SymbolRef},
-    types::{Alias, ArcType, Type, TypeEnv, TypeExt},
+    types::{Alias, ArcType, ModType, ModTypeRef, Type, TypeEnv, TypeExt},
 };
 
 pub use self::Instruction::*;
@@ -207,7 +207,7 @@ impl KindEnv for TypeInfos {
 impl TypeEnv for TypeInfos {
     type Type = ArcType;
 
-    fn find_type(&self, id: &SymbolRef) -> Option<&ArcType> {
+    fn find_type(&self, id: &SymbolRef) -> Option<ModTypeRef> {
         let id = id.definition_name();
         self.id_to_type
             .iter()
@@ -217,6 +217,7 @@ impl TypeEnv for TypeInfos {
             })
             .next()
             .map(|field| &field.typ)
+            .map(ModType::rigid)
     }
 
     fn find_type_info(&self, id: &SymbolRef) -> Option<&Alias<Symbol, ArcType>> {
diff --git a/vm/src/value.rs b/vm/src/value.rs
index dbd3a13f..a5370bf5 100644
--- a/vm/src/value.rs
+++ b/vm/src/value.rs
@@ -1610,7 +1610,7 @@ mod tests {
     use crate::base::{
         kind::{ArcKind, KindEnv},
         symbol::{Symbol, SymbolRef},
-        types::{Alias, ArcType, Field, Type, TypeEnv},
+        types::{Alias, ArcType, Field, ModTypeRef, Type, TypeEnv},
     };
 
     struct MockEnv(Option<Alias<Symbol, ArcType>>);
@@ -1624,7 +1624,7 @@ mod tests {
     impl TypeEnv for MockEnv {
         type Type = ArcType;
 
-        fn find_type(&self, _id: &SymbolRef) -> Option<&ArcType> {
+        fn find_type(&self, _id: &SymbolRef) -> Option<ModTypeRef> {
             None
         }
 
diff --git a/vm/src/vm.rs b/vm/src/vm.rs
index 29b8fdc8..ae35f19e 100644
--- a/vm/src/vm.rs
+++ b/vm/src/vm.rs
@@ -14,8 +14,8 @@ use crate::base::{
     metadata::{Metadata, MetadataEnv},
     symbol::{Name, Symbol, SymbolRef},
     types::{
-        Alias, AliasData, AppVec, ArcType, Generic, NullInterner, PrimitiveEnv, Type, TypeCache,
-        TypeEnv, TypeExt,
+        Alias, AliasData, AppVec, ArcType, Generic, ModType, ModTypeRef, NullInterner,
+        PrimitiveEnv, Type, TypeCache, TypeEnv, TypeExt,
     },
     DebugLevel,
 };
@@ -229,7 +229,7 @@ impl KindEnv for VmEnv {
 impl TypeEnv for VmEnv {
     type Type = ArcType;
 
-    fn find_type(&self, id: &SymbolRef) -> Option<&ArcType> {
+    fn find_type(&self, id: &SymbolRef) -> Option<ModTypeRef> {
         self.globals
             .get(id.definition_name())
             .map(|g| &g.typ)
@@ -247,6 +247,7 @@ impl TypeEnv for VmEnv {
                     .next()
                     .map(|ctor| ctor)
             })
+            .map(ModType::rigid)
     }
 
     fn find_type_info(&self, id: &SymbolRef) -> Option<&Alias<Symbol, ArcType>> {


Test patch:
diff --git a/base/tests/types.rs b/base/tests/types.rs
index cd99c29f..e62b21ea 100644
--- a/base/tests/types.rs
+++ b/base/tests/types.rs
@@ -347,7 +347,7 @@ impl KindEnv for MockEnv {
 impl TypeEnv for MockEnv {
     type Type = ArcType;
 
-    fn find_type(&self, _id: &SymbolRef) -> Option<&ArcType> {
+    fn find_type(&self, _id: &SymbolRef) -> Option<ModTypeRef> {
         None
     }
 
diff --git a/check/tests/implicits.rs b/check/tests/implicits.rs
index abb177de..8a29fe58 100644
--- a/check/tests/implicits.rs
+++ b/check/tests/implicits.rs
@@ -873,6 +873,31 @@ f 1
     assert!(result.is_ok(), "{}", result.unwrap_err());
 }
 
+#[test]
+fn allow_sub_classed_duplicate() {
+    let _ = ::env_logger::try_init();
+    let text = r#"
+#[implicit]
+type Base a = { x : a }
+#[implicit]
+type Derived a = { base : Base a, y : a }
+#[implicit]
+type Derived2 a = { derived : Derived a, z : a }
+
+let { ? } = 
+    let base : Base Int = { x = 0 }
+    let derived : Derived Int = { base, y = 1 }
+    let derived2 : Derived2 Int = { derived, z = 2 }
+    { base, derived, derived2 }
+
+let f ?b x : [Base a] -> a -> a = b.x
+f 1
+"#;
+    let result = support::typecheck(text);
+
+    assert!(result.is_ok(), "{}", result.unwrap_err());
+}
+
 test_check_err! {
 break_infinite_implicit_resolve_early,
     r#"
@@ -1000,6 +1025,32 @@ let transformer : Transformer (StateT s) =
 "()"
 }
 
+test_check! {
+unable_to_resolve_double_nested_instance,
+r#"
+#[implicit]
+type Functor f = {
+    map : forall a b . (a -> b) -> f a -> f b
+}
+#[implicit]
+type Applicative f = {
+    functor : Functor f,
+}
+#[implicit]
+type Monad m = { functor : Applicative m }
+
+let any x = any x
+
+let eval_state_t f : [Functor m] -> m a -> () = ()
+
+let associativity mx : [Monad m] -> m a -> () =
+    eval_state_t mx
+
+()
+"#,
+"()"
+}
+
 test_check! {
 match_inference,
 r#"
@@ -1020,3 +1071,46 @@ let f receiver : Channel Int -> _ =
 "#,
 "()"
 }
+
+test_check! {
+ord_array_implicit_resolution,
+r#"
+
+#[implicit]
+type Eq a = { (==) : a -> a -> Bool }
+
+#[implicit]
+type Ord a = { eq : Eq a, compare : a -> a -> () }
+
+let eq ?eq : [Eq a] -> Eq (Array a) =
+    { (==) = \x y -> False }
+
+let ord ?ord : [Ord a] -> Ord (Array a) =
+    let array_cmp l r = array_cmp l r
+    { eq, compare = \_ _ -> () }
+
+()
+"#,
+"()"
+}
+
+test_check! {
+ord_array_implicit_resolution2,
+r#"
+
+#[implicit]
+type Eq a = { (==) : a -> a -> Bool }
+
+#[implicit]
+type Ord a = { eq : Eq a, compare : a -> a -> () }
+
+let eq ?eq : [Eq a] -> Eq (Array a) =
+    { (==) = \x y -> False }
+
+let ord ?ord : [Ord a] -> Ord (Array a) =
+    { eq, compare = \_ _ -> () }
+
+()
+"#,
+"()"
+}
diff --git a/check/tests/support/mod.rs b/check/tests/support/mod.rs
index 295aeca3..6903d58d 100644
--- a/check/tests/support/mod.rs
+++ b/check/tests/support/mod.rs
@@ -14,7 +14,10 @@ use self::{
         metadata::{Metadata, MetadataEnv},
         pos::{BytePos, Spanned},
         symbol::{Symbol, SymbolModule, SymbolRef, Symbols},
-        types::{self, Alias, ArcType, Field, Generic, PrimitiveEnv, Type, TypeCache, TypeEnv},
+        types::{
+            self, Alias, ArcType, Field, Generic, ModType, ModTypeRef, PrimitiveEnv, Type,
+            TypeCache, TypeEnv,
+        },
     },
     check::{
         metadata, rename,
@@ -122,9 +125,9 @@ impl KindEnv for MockEnv {
 
 impl TypeEnv for MockEnv {
     type Type = ArcType;
-    fn find_type(&self, id: &SymbolRef) -> Option<&ArcType> {
+    fn find_type(&self, id: &SymbolRef) -> Option<ModTypeRef> {
         match id.definition_name() {
-            "False" | "True" => Some(&self.bool.as_type()),
+            "False" | "True" => Some(ModType::rigid(&self.bool.as_type())),
             _ => None,
         }
     }
diff --git a/completion/tests/support/mod.rs b/completion/tests/support/mod.rs
index 8602ffce..5f587df8 100644
--- a/completion/tests/support/mod.rs
+++ b/completion/tests/support/mod.rs
@@ -9,7 +9,9 @@ use crate::base::{
     metadata::{Metadata, MetadataEnv},
     pos::BytePos,
     symbol::{Symbol, SymbolModule, SymbolRef, Symbols},
-    types::{self, Alias, ArcType, Generic, PrimitiveEnv, Type, TypeCache, TypeEnv},
+    types::{
+        self, Alias, ArcType, Generic, ModType, ModTypeRef, PrimitiveEnv, Type, TypeCache, TypeEnv,
+    },
 };
 
 use crate::check::{
@@ -87,11 +89,11 @@ impl KindEnv for MockEnv {
 impl TypeEnv for MockEnv {
     type Type = ArcType;
 
-    fn find_type(&self, id: &SymbolRef) -> Option<&ArcType> {
+    fn find_type(&self, id: &SymbolRef) -> Option<ModTypeRef> {
         match id.definition_name() {
-            "False" | "True" => Some(self.bool.as_type()),
+            "False" | "True" => Some(ModType::rigid(self.bool.as_type())),
             // Just need a dummy type that is not `Type::hole` to verify that lookups work
-            "std.prelude" => Some(&self.int),
+            "std.prelude" => Some(ModType::rigid(&self.int)),
             _ => None,
         }
     }