Repository: gluon-lang/gluon
Pull request #671 (2019-01-03 20:18:55)

fix(check): Abort implicit checking immediately on infinite loops
There may be some quirks to workout but everything in the gluon repo
itself works fine. This avoids the huge error messages generated when
implicit resolution ends up in an infinite loop.


Patch:
diff --git a/base/src/scoped_map.rs b/base/src/scoped_map.rs
index 9b52d444..71e83a69 100644
--- a/base/src/scoped_map.rs
+++ b/base/src/scoped_map.rs
@@ -1,7 +1,6 @@
 //! A map data type which allows the same key to exist at multiple scope levels
 use std::borrow::Borrow;
-use std::collections::hash_map;
-use std::collections::hash_map::{Entry, IterMut};
+use std::collections::hash_map::{self, IterMut};
 use std::fmt;
 use std::hash::Hash;
 
@@ -131,6 +130,13 @@ impl<K: Eq + Hash + Clone, V> ScopedMap<K, V> {
         self.map.get(k).map(|x| &x[..])
     }
 
+    pub fn entry(&mut self, key: K) -> Entry<K, V> {
+        match self.map.entry(key) {
+            hash_map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry(entry)),
+            hash_map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry(entry)),
+        }
+    }
+
     pub fn contains_key<'a, Q: ?Sized>(&'a self, k: &Q) -> bool
     where
         K: Borrow<Q>,
@@ -159,8 +165,8 @@ impl<K: Eq + Hash + Clone, V> ScopedMap<K, V> {
     /// Swaps the value stored at key, or inserts it if it is not present
     pub fn swap(&mut self, k: K, v: V) -> Option<V> {
         let vec = match self.map.entry(k.clone()) {
-            Entry::Occupied(v) => v.into_mut(),
-            Entry::Vacant(v) => v.insert(Vec::new()),
+            hash_map::Entry::Occupied(v) => v.into_mut(),
+            hash_map::Entry::Vacant(v) => v.insert(Vec::new()),
         };
         if vec.is_empty() {
             vec.push(v);
@@ -198,8 +204,8 @@ impl<K: Eq + Hash + Clone, V> ScopedMap<K, V> {
 
     pub fn insert(&mut self, k: K, v: V) -> bool {
         let vec = match self.map.entry(k.clone()) {
-            Entry::Occupied(v) => v.into_mut(),
-            Entry::Vacant(v) => v.insert(Vec::new()),
+            hash_map::Entry::Occupied(v) => v.into_mut(),
+            hash_map::Entry::Vacant(v) => v.insert(Vec::new()),
         };
         vec.push(v);
         self.scopes.push(Some(k));
@@ -231,6 +237,42 @@ impl<K: Eq + Hash + Clone, V> Extend<(K, V)> for ScopedMap<K, V> {
     }
 }
 
+pub enum Entry<'a, K, V> {
+    Vacant(VacantEntry<'a, K, V>),
+    Occupied(OccupiedEntry<'a, K, V>),
+}
+
+pub struct VacantEntry<'a, K, V>(hash_map::VacantEntry<'a, K, Vec<V>>);
+pub struct OccupiedEntry<'a, K, V>(hash_map::OccupiedEntry<'a, K, Vec<V>>);
+
+impl<'a, K, V> VacantEntry<'a, K, V> {
+    pub fn insert(self, value: V) -> &'a mut V {
+        &mut self.0.insert(vec![value])[0]
+    }
+}
+
+impl<'a, K, V> OccupiedEntry<'a, K, V> {
+    pub fn key(&self) -> &K {
+        self.0.key()
+    }
+
+    pub fn get(&self) -> &V {
+        self.0.get().last().unwrap()
+    }
+
+    pub fn get_mut(&mut self) -> &mut V {
+        self.0.get_mut().last_mut().unwrap()
+    }
+
+    pub fn into_mut(self) -> &'a mut V {
+        self.0.into_mut().last_mut().unwrap()
+    }
+
+    pub fn insert(&mut self, value: V) {
+        self.0.get_mut().push(value);
+    }
+}
+
 pub struct Iter<'a, K, V>
 where
     K: 'a,
diff --git a/check/src/implicits.rs b/check/src/implicits.rs
index 71797425..51281e4c 100644
--- a/check/src/implicits.rs
+++ b/check/src/implicits.rs
@@ -1,7 +1,9 @@
-use std::borrow::Borrow;
-use std::cmp::Ordering;
-use std::fmt;
-use std::hash::{Hash, Hasher};
+use std::{
+    borrow::Borrow,
+    cmp::Ordering,
+    fmt,
+    hash::{Hash, Hasher},
+};
 
 use itertools::{Either, Itertools};
 
@@ -9,20 +11,23 @@ use rpds;
 
 use codespan_reporting::{Diagnostic, Label};
 
-use crate::base::ast::{self, Expr, MutVisitor, SpannedExpr, TypedIdent};
-use crate::base::error::AsDiagnostic;
-use crate::base::fnv::FnvMap;
-use crate::base::metadata::Metadata;
-use crate::base::pos::{self, BytePos, Span, Spanned};
-use crate::base::resolve;
-use crate::base::scoped_map::ScopedMap;
-use crate::base::symbol::{Symbol, SymbolRef};
-use crate::base::types::{self, ArcType, ArgType, BuiltinType, Type};
-
-use crate::substitution::Substitution;
-use crate::typecheck::{TypeError, Typecheck, TypecheckEnv};
-
-const MAX_IMPLICIT_LEVEL: u32 = 20;
+use crate::base::{
+    ast::{self, Expr, MutVisitor, SpannedExpr, TypedIdent},
+    error::AsDiagnostic,
+    fnv::FnvMap,
+    metadata::Metadata,
+    pos::{self, BytePos, Span, Spanned},
+    resolve,
+    scoped_map::{self, ScopedMap},
+    symbol::{Symbol, SymbolRef},
+    types::{self, ArcType, ArgType, BuiltinType, Type},
+};
+
+use crate::{
+    substitution::Substitution,
+    typecheck::{TypeError, Typecheck, TypecheckEnv},
+    unify_type::{self, Size},
+};
 
 impl SymbolKey {
     pub fn new(typ: &ArcType) -> Option<SymbolKey> {
@@ -151,7 +156,10 @@ impl ImplicitBindings {
         update_vec(&mut self.rest, &mut f);
     }
 
-    fn iter<'a>(&'a self, typ: &ArcType) -> impl DoubleEndedIterator<Item = &'a ImplicitBinding> {
+    fn get_candidates<'a>(
+        &'a self,
+        typ: &ArcType,
+    ) -> impl DoubleEndedIterator<Item = &'a ImplicitBinding> {
         match SymbolKey::new(&typ) {
             Some(symbol) => Either::Left(self.partioned.get(&symbol).unwrap_or(&self.rest).iter()),
             None => Either::Right(
@@ -236,6 +244,86 @@ struct ResolveImplicitsVisitor<'a, 'b: 'a> {
 }
 
 impl<'a, 'b> ResolveImplicitsVisitor<'a, 'b> {
+    fn resolve_implicit(
+        &mut self,
+        implicit_bindings: &ImplicitBindings,
+        expr: &SpannedExpr<Symbol>,
+        id: &TypedIdent<Symbol>,
+    ) -> Option<SpannedExpr<Symbol>> {
+        debug!(
+            "Resolving {} against:\n{}",
+            id.typ,
+            implicit_bindings
+                .get_candidates(&id.typ)
+                .map(|t| &t.1)
+                .format("\n")
+        );
+        self.tc.implicit_resolver.visited.clear();
+        let span = expr.span;
+        let mut to_resolve = Vec::new();
+        match self.find_implicit(
+            &implicit_bindings,
+            &mut to_resolve,
+            &Demand {
+                reason: rpds::List::new(),
+                constraint: id.typ.clone(),
+            },
+        ) {
+            Ok(path_of_candidate) => {
+                debug!(
+                    "Found implicit candidate `{}`. Trying its implicit arguments (if any)",
+                    path_of_candidate
+                        .iter()
+                        .rev()
+                        .map(|id| &id.name)
+                        .format(".")
+                );
+
+                let resolution_result = match self.resolve_implicit_application(
+                    0,
+                    &implicit_bindings,
+                    span,
+                    &path_of_candidate,
+                    &to_resolve,
+                ) {
+                    Ok(opt) => opt.map(Ok),
+                    Err(err) => Some(Err(err)),
+                };
+
+                match resolution_result {
+                    Some(Ok(replacement)) => Some(replacement),
+                    Some(Err(err)) => {
+                        self.tc.errors.push(Spanned {
+                            span: expr.span,
+                            value: TypeError::UnableToResolveImplicit(err).into(),
+                        });
+                        None
+                    }
+                    None => {
+                        debug!("UnableToResolveImplicit {:?} {}", id.name, id.typ);
+                        self.tc.errors.push(Spanned {
+                            span: expr.span,
+                            value: TypeError::UnableToResolveImplicit(Error {
+                                kind: ErrorKind::MissingImplicit(id.typ.clone()),
+                                reason: to_resolve
+                                    .first()
+                                    .map_or_else(rpds::List::new, |demand| demand.reason.clone()),
+                            })
+                            .into(),
+                        });
+                        None
+                    }
+                }
+            }
+            Err(err) => {
+                self.tc.errors.push(Spanned {
+                    span: expr.span,
+                    value: TypeError::UnableToResolveImplicit(err).into(),
+                });
+                None
+            }
+        }
+    }
     fn resolve_implicit_application(
         &mut self,
         level: u32,
@@ -261,16 +349,6 @@ impl<'a, 'b> ResolveImplicitsVisitor<'a, 'b> {
         path: &[TypedIdent<Symbol>],
         to_resolve: &[Demand],
     ) -> Result<Option<SpannedExpr<Symbol>>> {
-        match to_resolve.first() {
-            Some(demand) if level > MAX_IMPLICIT_LEVEL => {
-                return Err(Error {
-                    kind: ErrorKind::LoopInImplicitResolution(Vec::new()),
-                    reason: demand.reason.clone(),
-                });
-            }
-            _ => (),
-        }
-
         let base_ident = path[0].clone();
         let func = path[1..].iter().fold(
             pos::spanned(span, Expr::Ident(base_ident)),
@@ -288,6 +366,8 @@ impl<'a, 'b> ResolveImplicitsVisitor<'a, 'b> {
             let resolved_arguments = to_resolve
                 .iter()
                 .filter_map(|demand| {
+                    self.tc.implicit_resolver.visited.enter_scope();
+
                     let mut to_resolve = Vec::new();
                     let result = self
                         .find_implicit(implicit_bindings, &mut to_resolve, demand)
@@ -302,12 +382,15 @@ impl<'a, 'b> ResolveImplicitsVisitor<'a, 'b> {
                             )
                         });
 
+                    self.tc.implicit_resolver.visited.exit_scope();
+
                     match result {
                         Ok(opt) => opt.map(Ok),
                         Err(err) => Some(Err(err)),
                     }
                 })
                 .collect::<Result<Vec<_>>>()?;
+
             if resolved_arguments.len() == to_resolve.len() {
                 Some(pos::spanned(
                     span,
@@ -323,25 +406,27 @@ impl<'a, 'b> ResolveImplicitsVisitor<'a, 'b> {
         })
     }
 
-    fn try_implicit(
+    fn try_resolve_implicit(
         &mut self,
         path: &[TypedIdent<Symbol>],
         to_resolve: &mut Vec<Demand>,
         demand: &Demand,
-        typ: &ArcType,
+        binding_type: &ArcType,
     ) -> bool {
         debug!(
-            "Trying implicit `{}` : {}",
+            "Trying implicit {{\n    path: `{}`,\n    to_resolve: [{}],\n    demand: `{}`,\n    binding_type: {} }}",
             path.iter().map(|id| &id.name).format("."),
-            typ,
+            to_resolve.iter().map(|d| &d.constraint).format(", "),
+            self.tc.subs.zonk(&demand.constraint),
+            binding_type,
         );
 
-        let typ = self.tc.new_skolem_scope(typ);
-        let typ = self.tc.instantiate_generics(&typ);
+        let binding_type = self.tc.new_skolem_scope(binding_type);
+        let binding_type = self.tc.instantiate_generics(&binding_type);
         to_resolve.clear();
-        let mut iter = types::implicit_arg_iter(&typ);
+        let mut iter = types::implicit_arg_iter(&binding_type);
         to_resolve.extend(iter.by_ref().cloned().map(|constraint| Demand {
-            reason: demand.reason.push_front(typ.clone()),
+            reason: demand.reason.push_front(binding_type.clone()),
             constraint,
         }));
 
@@ -356,15 +441,58 @@ impl<'a, 'b> ResolveImplicitsVisitor<'a, 'b> {
         to_resolve: &mut Vec<Demand>,
         demand: &Demand,
     ) -> Result<&'c [TypedIdent<Symbol>]> {
-        let mut iter = implicit_bindings.iter(&demand.constraint).rev();
-        let found_candidate = iter
+        let mut candidates = implicit_bindings.get_candidates(&demand.constraint).rev();
+        let found_candidate = candidates
             .by_ref()
-            .find(|&&(ref path, ref typ)| self.try_implicit(path, to_resolve, demand, typ));
+            .find(|&&(ref path, ref typ)| self.try_resolve_implicit(path, to_resolve, demand, typ));
         match found_candidate {
-            Some(candidate) => {
-                let mut additional_candidates: Vec<_> = iter
+            Some((candidate_path, candidate_type)) => {
+                let new_demands = to_resolve
+                    .iter()
+                    .map(|d| self.tc.subs.zonk(&d.constraint))
+                    .collect::<Vec<_>>()
+                    .into_boxed_slice();
+
+                match self.tc.implicit_resolver.visited.entry(
+                    candidate_path
+                        .iter()
+                        .map(|id| id.name.clone())
+                        .collect::<Vec<_>>()
+                        .into_boxed_slice(),
+                ) {
+                    scoped_map::Entry::Vacant(entry) => {
+                        entry.insert(new_demands);
+                    }
+                    scoped_map::Entry::Occupied(mut entry) => {
+                        trace!(
+                            "Smaller check: [{}] < [{}]",
+                            new_demands.iter().format(", "),
+                            entry.get().iter().format(", "),
+                        );
+
+                        let state = unify_type::State::new(
+                            &self.tc.environment,
+                            &self.tc.subs,
+                            &self.tc.type_cache,
+                        );
+                        if !smallers(state, &new_demands, entry.get()) {
+                            return Err(Error {
+                                kind: ErrorKind::LoopInImplicitResolution(vec![candidate_path
+                                    .iter()
+                                    .map(|id| &id.name)
+                                    .format(".")
+                                    .to_string()]),
+                                reason: demand.reason.clone(),
+                            });
+                        }
+                        // Update the demands with to these new, smaller demands
+                        entry.insert(new_demands);
+                    }
+                }
+
+                let mut additional_candidates: Vec<_> = candidates
                     .filter(|&&(ref path, ref typ)| {
-                        self.try_implicit(path, &mut Vec::new(), demand, typ)
+                        self.try_resolve_implicit(path, &mut Vec::new(), demand, typ)
                     })
                     .map(|bind| {
                         (
@@ -374,16 +502,15 @@ impl<'a, 'b> ResolveImplicitsVisitor<'a, 'b> {
                     })
                     .collect();
                 if additional_candidates.is_empty() {
-                    Ok(&candidate.0)
+                    Ok(&candidate_path)
                 } else {
                     additional_candidates.push((
-                        candidate
-                            .0
+                        candidate_path
                             .iter()
                             .map(|id| &id.name)
                             .format(".")
                             .to_string(),
-                        candidate.1.clone(),
+                        candidate_type.clone(),
                     ));
                     Err(Error {
                         kind: ErrorKind::AmbiguousImplicit(additional_candidates),
@@ -404,7 +531,7 @@ impl<'a, 'b, 'c> MutVisitor<'c> for ResolveImplicitsVisitor<'a, 'b> {
 
     fn visit_expr(&mut self, expr: &mut SpannedExpr<Symbol>) {
         let mut replacement = None;
-        if let Expr::Ident(ref mut id) = expr.value {
+        if let Expr::Ident(ref id) = expr.value {
             let implicit_bindings = self
                 .tc
                 .implicit_resolver
@@ -412,76 +539,7 @@ impl<'a, 'b, 'c> MutVisitor<'c> for ResolveImplicitsVisitor<'a, 'b> {
                 .get(&id.name)
                 .cloned();
             if let Some(implicit_bindings) = implicit_bindings {
-                debug!(
-                    "Resolving {} against:\n{}",
-                    id.typ,
-                    implicit_bindings.iter(&id.typ).map(|t| &t.1).format("\n")
-                );
-                let span = expr.span;
-                let mut to_resolve = Vec::new();
-                match self.find_implicit(
-                    &implicit_bindings,
-                    &mut to_resolve,
-                    &Demand {
-                        reason: rpds::List::new(),
-                        constraint: id.typ.clone(),
-                    },
-                ) {
-                    Ok(path_of_candidate) => {
-                        debug!(
-                            "Found implicit candidate `{}`. Trying its implicit arguments (if any)",
-                            path_of_candidate
-                                .iter()
-                                .rev()
-                                .map(|id| &id.name)
-                                .format(".")
-                        );
-
-                        let resolution_result = match self.resolve_implicit_application(
-                            0,
-                            &implicit_bindings,
-                            span,
-                            &path_of_candidate,
-                            &to_resolve,
-                        ) {
-                            Ok(opt) => opt.map(Ok),
-                            Err(err) => Some(Err(err)),
-                        };
-
-                        replacement = match resolution_result {
-                            Some(Ok(replacement)) => Some(replacement),
-                            Some(Err(err)) => {
-                                self.tc.errors.push(Spanned {
-                                    span: expr.span,
-                                    value: TypeError::UnableToResolveImplicit(err).into(),
-                                });
-                                None
-                            }
-                            None => {
-                                debug!("UnableToResolveImplicit {:?} {}", id.name, id.typ);
-                                self.tc.errors.push(Spanned {
-                                    span: expr.span,
-                                    value: TypeError::UnableToResolveImplicit(Error {
-                                        kind: ErrorKind::MissingImplicit(id.typ.clone()),
-                                        reason: to_resolve
-                                            .first()
-                                            .map_or_else(rpds::List::new, |demand| {
-                                                demand.reason.clone()
-                                            }),
-                                    })
-                                    .into(),
-                                });
-                                None
-                            }
-                        };
-                    }
-                    Err(err) => {
-                        self.tc.errors.push(Spanned {
-                            span: expr.span,
-                            value: TypeError::UnableToResolveImplicit(err).into(),
-                        });
-                    }
-                }
+                replacement = self.resolve_implicit(&implicit_bindings, expr, id);
             }
         }
         if let Some(replacement) = replacement {
@@ -499,6 +557,7 @@ pub struct ImplicitResolver<'a> {
     environment: &'a TypecheckEnv,
     pub(crate) implicit_bindings: Vec<ImplicitBindings>,
     implicit_vars: ScopedMap<Symbol, ImplicitBindings>,
+    visited: ScopedMap<Box<[Symbol]>, Box<[ArcType]>>,
 }
 
 impl<'a> ImplicitResolver<'a> {
@@ -511,6 +570,7 @@ impl<'a> ImplicitResolver<'a> {
             environment,
             implicit_bindings: Vec::new(),
             implicit_vars: ScopedMap::new(),
+            visited: Default::default(),
         }
     }
 
@@ -659,3 +719,28 @@ pub fn resolve(tc: &mut Typecheck, expr: &mut SpannedExpr<Symbol>) {
     let mut visitor = ResolveImplicitsVisitor { tc };
     visitor.visit_expr(expr);
 }
+
+fn smaller(state: unify_type::State, new_type: &ArcType, old_type: &ArcType) -> Size {
+    match unify_type::smaller(state.clone(), new_type, old_type) {
+        Size::Smaller => match unify_type::smaller(state, old_type, new_type) {
+            Size::Smaller => Size::Different,
+            _ => Size::Smaller,
+        },
+        check => check,
+    }
+}
+fn smallers(state: unify_type::State, new_types: &[ArcType], old_types: &[ArcType]) -> bool {
+    if old_types.is_empty() {
+        true
+    } else {
+        old_types
+            .iter()
+            .zip(new_types)
+            .fold(Size::Equal, |acc, (old, new)| match acc {
+                Size::Different => Size::Different,
+                Size::Smaller => Size::Smaller,
+                Size::Equal => smaller(state.clone(), new, old),
+            })
+            == Size::Smaller
+    }
+}
diff --git a/check/src/substitution.rs b/check/src/substitution.rs
index 5b6ef512..429f703f 100644
--- a/check/src/substitution.rs
+++ b/check/src/substitution.rs
@@ -5,8 +5,7 @@ use std::fmt;
 use union_find::{QuickFindUf, Union, UnionByRank, UnionFind, UnionResult};
 
 use crate::base::fixed::{FixedMap, FixedVec};
-use crate::base::types;
-use crate::base::types::{ArcType, Type, Walker};
+use crate::base::types::{self, ArcType, Type, Walker};
 
 #[derive(Debug, PartialEq)]
 pub enum Error<T> {
@@ -398,3 +397,15 @@ impl<T: Substitutable + PartialEq + Clone> Substitution<T> {
         Ok(resolved_type.cloned())
     }
 }
+
+impl Substitution<ArcType> {
+    pub fn zonk(&self, typ: &ArcType) -> ArcType {
+        types::walk_move_type(typ.clone(), &mut |typ| match typ.get_var() {
+            Some(var) => match self.find_type_for_var(var.get_id()) {
+                Some(t) => Some(self.zonk(t)),
+                None => None,
+            },
+            None => None,
+        })
+    }
+}
diff --git a/check/src/unify_type.rs b/check/src/unify_type.rs
index d50f2e49..a5af8d0e 100644
--- a/check/src/unify_type.rs
+++ b/check/src/unify_type.rs
@@ -1,19 +1,22 @@
 use std::{borrow::Cow, fmt, mem};
 
-use crate::base::error::Errors;
-use crate::base::fnv::FnvMap;
-use crate::base::kind::ArcKind;
-use crate::base::merge;
-use crate::base::resolve::{self, Error as ResolveError};
-use crate::base::symbol::{Symbol, SymbolRef};
-use crate::base::types::{
-    self, AppVec, ArcType, ArgType, BuiltinType, Field, Filter, Generic, Skolem, Type, TypeCache,
-    TypeEnv, TypeFormatter, TypeVariable,
+use crate::base::{
+    error::Errors,
+    fnv::FnvMap,
+    kind::ArcKind,
+    merge,
+    resolve::{self, Error as ResolveError},
+    symbol::{Symbol, SymbolRef},
+    types::{
+        self, walk_move_type_opt, AppVec, ArcType, ArgType, BuiltinType, Field, Filter, Generic,
+        Skolem, Type, TypeCache, TypeEnv, TypeFormatter, TypeVariable,
+    },
 };
 
-use crate::substitution::{Substitutable, Substitution, Variable, VariableFactory};
-use crate::unify;
-use crate::unify::{Error as UnifyError, GenericVariant, Unifiable, Unifier};
+use crate::{
+    substitution::{Substitutable, Substitution, Variable, VariableFactory},
+    unify::{self, Error as UnifyError, GenericVariant, Unifiable, Unifier},
+};
 
 use smallvec::SmallVec;
 
@@ -1176,6 +1179,29 @@ pub fn subsumes(
     }
 }
 
+pub fn subsumes_no_subst(
+    state: State,
+    l: &ArcType,
+    r: &ArcType,
+) -> Result<ArcType, (ArcType, Errors<Error<Symbol>>)> {
+    debug!("Subsume {} <=> {}", l, r);
+    let mut unifier = UnifierState {
+        unifier: Subsume {
+            subs: state.subs,
+            errors: Errors::new(),
+            allow_returned_type_replacement: true,
+        },
+        state: state,
+    };
+
+    let typ = unifier.try_match(l, r);
+    if unifier.unifier.errors.has_errors() {
+        Err((typ.unwrap_or_else(|| l.clone()), unifier.unifier.errors))
+    } else {
+        Ok(typ.unwrap_or_else(|| l.clone()))
+    }
+}
+
 struct Subsume<'e> {
     subs: &'e Substitution<ArcType>,
     errors: Errors<Error<Symbol>>,
@@ -1339,6 +1365,139 @@ fn reconstruct_forall(
     Type::forall_with_vars(new_params, inner_type, Some(new_vars))
 }
 
+pub fn equal(state: State, l: &ArcType, r: &ArcType) -> bool {
+    trace!("Equal {} <=> {}", l, r);
+    let mut unifier = UnifierState {
+        unifier: Equal {
+            subs: state.subs,
+            equal: true,
+        },
+        state,
+    };
+
+    unifier.try_match(l, r);
+    unifier.unifier.equal
+}
+
+struct Equal<'e> {
+    subs: &'e Substitution<ArcType>,
+    equal: bool,
+}
+
+impl<'a, 'e> Unifier<State<'a>, ArcType> for UnifierState<'a, Equal<'e>> {
+    fn report_error(&mut self, error: UnifyError<ArcType, TypeError<Symbol>>) {
+        debug!("Equal: Error {}", error);
+        self.unifier.equal = false;
+    }
+
+    fn try_match_res(
+        &mut self,
+        l: &ArcType,
+        r: &ArcType,
+    ) -> Result<Option<ArcType>, UnifyError<ArcType, TypeError<Symbol>>> {
+        let subs = self.unifier.subs;
+        let l = subs.real(l);
+        let r = subs.real(r);
+        debug!("{} <=> {}", l, r);
+        l.zip_match(r, self)
+    }
+
+    fn error_type(&self) -> ArcType {
+        ArcType::error_type(&self.state)
+    }
+}
+
+pub fn smaller(state: State, new_type: &ArcType, old_type: &ArcType) -> Size {
+    trace!("smaller: {} < {}", new_type, old_type);
+    let mut unifier = UnifierState {
+        unifier: Smaller {
+            size: Size::Equal,
+            just_encountered_error: false,
+        },
+        state,
+    };
+
+    unifier.try_match(new_type, old_type);
+    let size = unifier.unifier.size;
+    trace!("smaller return: {:?}", size);
+    size
+}
+
+#[derive(PartialEq, Debug)]
+pub enum Size {
+    Smaller,
+    Equal,
+    Different,
+}
+
+struct Smaller {
+    size: Size,
+    just_encountered_error: bool,
+}
+
+impl<'a, 'e> Unifier<State<'a>, ArcType> for UnifierState<'a, Smaller> {
+    fn report_error(&mut self, error: UnifyError<ArcType, TypeError<Symbol>>) {
+        debug!("Smaller: Error {}", error);
+    }
+
+    fn try_match_res(
+        &mut self,
+        l: &ArcType,
+        r: &ArcType,
+    ) -> Result<Option<ArcType>, UnifyError<ArcType, TypeError<Symbol>>> {
+        if self.unifier.size == Size::Different {
+            return Ok(None);
+        }
+        trace!("{} <=> {}", l, r);
+
+        match (&**l, &**r) {
+            // zip_match substitutes variables so we need to intercept variables here and compare
+            // them manually
+            (Type::Variable(_), _) | (_, Type::Variable(_)) => {
+                if l != r {
+                    self.unifier.size = Size::Different;
+                }
+                Ok(None)
+            }
+
+            _ => match l.zip_match(r, self) {
+                Err(_) => {
+                    self.unifier.size = Size::Different;
+                    walk_move_type_opt(r, &mut |inner_type: &ArcType| {
+                        if inner_type == l {
+                            self.unifier.size = Size::Smaller
+                        }
+                        None
+                    });
+                    if self.unifier.size == Size::Different {
+                        self.unifier.just_encountered_error = true;
+                    }
+                    Ok(None)
+                }
+                result => {
+                    if self.unifier.just_encountered_error {
+                        self.unifier.just_encountered_error = false;
+                        // We ended up finding a mismatch inside this type so we need to try the check
+                        // again in case the only cause for the error is that we resolved an alias
+                        // which then mismatched
+                        walk_move_type_opt(r, &mut |inner_type: &ArcType| {
+                            if inner_type == l {
+                                self.unifier.size = Size::Smaller
+                            }
+                            None
+                        });
+                    }
+                    result
+                }
+            },
+        }
+    }
+
+    fn error_type(&self) -> ArcType {
+        ArcType::error_type(&self.state)
+    }
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;


Test patch:
diff --git a/check/tests/implicits.rs b/check/tests/implicits.rs
index 2e761912..217797dd 100644
--- a/check/tests/implicits.rs
+++ b/check/tests/implicits.rs
@@ -596,7 +596,7 @@ let monad : Monad List =
 
 let fold_m monad f z w : forall a b m t . [Foldable t] -> Monad m -> (a -> b -> m a) -> a -> t b -> () = ()
 
-let fold_m2 ?x : [Foldable t] -> _ = fold_m monad
+let fold_m2 ?x : [Foldable t] -> _ -> _ -> t b -> _ = fold_m monad
 
 let f x : List Int -> _ = fold_m2 (\a b -> Cons a Nil) x
 f
@@ -872,3 +872,86 @@ f 1
 
     assert!(result.is_ok(), "{}", result.unwrap_err());
 }
+
+test_check_err! {
+break_infinte_implicit_resolve_early,
+    r#"
+#[implicit]
+type Implicit a = { f : a -> String } 
+
+type Test a = { x : a }
+
+let any x = any x
+
+let test : [Implicit a] -> Implicit (Test a) = any ()
+
+let f : [Implicit a] -> a -> () = any ()
+
+f (any ())
+"#,
+TypeError::UnableToResolveImplicit(ImplicitError {
+    kind: ImplicitErrorKind::LoopInImplicitResolution(..),
+    ..
+})
+}
+
+test_check! {
+one_binding_used_twice,
+r#"
+#[implicit]
+type Test a = | Test a
+
+type Pair a b = { x : a, y : b }
+
+let any x = any x
+
+let pair_test: [Test a] -> [Test b] -> Test (Pair a b) = any ()
+let int_test: Test Int = Test 1
+
+let test x : [Test a] -> a -> () = ()
+
+test { x = 1, y = 2 }
+"#,
+"()"
+}
+
+test_check! {
+one_binding_nested_1,
+r#"
+#[implicit]
+type Test a = | Test a
+
+type Value a = { x : a }
+
+let any x = any x
+
+let value_test: [Test a] -> Test (Value a) = any ()
+let int_test: Test Int = Test 1
+
+let test x : [Test a] -> a -> () = ()
+
+test { x = { x = 1 } }
+"#,
+"()"
+}
+
+test_check! {
+one_binding_nested_2,
+r#"
+#[implicit]
+type Test a = | Test a
+
+type Value a = { x : a }
+
+let any x = any x
+
+let value_test: [Test a] -> Test (Value a) = any ()
+let value_test: [Test a] -> Test (Array a) = any ()
+let int_test: Test Int = Test 1
+
+let test x : [Test a] -> a -> () = ()
+
+test { x = [{ x = 1 }] }
+"#,
+"()"
+}
diff --git a/check/tests/support/mod.rs b/check/tests/support/mod.rs
index d5ba7dcf..fd7a0378 100644
--- a/check/tests/support/mod.rs
+++ b/check/tests/support/mod.rs
@@ -6,9 +6,10 @@ extern crate codespan;
 use crate::base::{
     self,
     ast::{DisplayEnv, Expr, IdentEnv, SpannedExpr},
-    error::InFile,
+    error::{Errors, InFile},
     kind::{ArcKind, Kind, KindEnv},
     metadata::{Metadata, MetadataEnv},
+    pos::{BytePos, Spanned},
     symbol::{Symbol, SymbolModule, SymbolRef, Symbols},
     types::{self, Alias, ArcType, Field, Generic, PrimitiveEnv, Type, TypeCache, TypeEnv},
 };
@@ -20,7 +21,7 @@ use crate::check::{
     typecheck::{self, Typecheck},
 };
 
-use std::{cell::RefCell, marker::PhantomData, rc::Rc};
+use std::{cell::RefCell, fmt, marker::PhantomData, rc::Rc};
 
 quick_error! {
     /// Representation of all possible errors that can occur when interacting with the `vm` crate
@@ -169,6 +170,15 @@ where
     }
 }
 
+pub(crate) fn in_file_error<E>(text: &str, errors: Errors<Spanned<E, BytePos>>) -> InFile<E>
+where
+    E: fmt::Display,
+{
+    let mut source = codespan::CodeMap::new();
+    source.add_filemap("test".into(), text.into());
+    InFile::new(source, errors)
+}
+
 pub fn typecheck_expr_expected(
     text: &str,
     expected: Option<&ArcType>,
@@ -176,9 +186,7 @@ pub fn typecheck_expr_expected(
     let mut expr = match parse_new(text) {
         Ok(expr) => expr,
         Err((expr, err)) => {
-            let mut source = codespan::CodeMap::new();
-            source.add_filemap("test".into(), text.into());
-            let err = InFile::new(source, err);
+            let err = in_file_error(text, err);
             return (expr.unwrap_or_else(|| panic!("{}", err)), Err(err.into()));
         }
     };
@@ -204,14 +212,7 @@ pub fn typecheck_expr_expected(
 
     let result = tc.typecheck_expr_expected(&mut expr, expected);
 
-    (
-        expr,
-        result.map_err(|err| {
-            let mut source = codespan::CodeMap::new();
-            source.add_filemap("test".into(), text.into());
-            InFile::new(source, err).into()
-        }),
-    )
+    (expr, result.map_err(|err| in_file_error(text, err).into()))
 }
 
 pub fn typecheck_expr(text: &str) -> (SpannedExpr<Symbol>, Result<ArcType, Error>) {
@@ -252,14 +253,7 @@ pub fn typecheck_partial_expr(
 
     let result = tc.typecheck_expr(&mut expr);
 
-    (
-        expr,
-        result.map_err(|err| {
-            let mut source = codespan::CodeMap::new();
-            source.add_filemap("test".into(), text.into());
-            InFile::new(source, err)
-        }),
-    )
+    (expr, result.map_err(|err| in_file_error(text, err)))
 }
 
 #[allow(dead_code)]
@@ -402,13 +396,16 @@ macro_rules! test_check_err {
             let _ = env_logger::try_init();
             let text = $source;
             let result = support::typecheck(text);
-            assert_err!(result, $($id),+);
+            assert_err!([$source] result, $($id),+);
         }
     };
 }
 
 macro_rules! assert_err {
-    ($e: expr, $($id: pat),+) => {{
+    ($e: expr, $($id: pat),+) => {
+        assert_err!([""] $e, $($id),+)
+    };
+    ([$text: expr] $e: expr, $($id: pat),+) => {{
         #[allow(unused_imports)]
         use crate::check::{
             typecheck::TypeError::*,
@@ -428,8 +425,23 @@ macro_rules! assert_err {
                 $(
                 match iter.next() {
                     Some(&crate::base::pos::Spanned { value: crate::base::error::Help { error: $id, .. }, .. }) => (),
-                    _ => assert!(false, "Found errors:\n{}\nbut expected {}",
-                                        errors, stringify!($id)),
+                    _ => {
+                        if $text.is_empty() {
+                            assert!(
+                                false,
+                                "Found errors:\n{}\nbut expected {}",
+                                errors,
+                                stringify!($id)
+                            )
+                        } else {
+                            assert!(
+                                false,
+                                "Found errors:\n{}\nbut expected {}",
+                                crate::support::in_file_error($text, errors),
+                                stringify!($id)
+                            )
+                        }
+                    }
                 }
                 )+
                 assert!(iter.count() == 0, "Found more errors than expected\n{}", errors);