HIR Typecheck - Deduplicate IVar handling

5 files changed, 871 insertions, 219 deletions

diff --git a/src/hir_typeck/expr.hpp b/src/hir_typeck/expr.hpp
index 1eaeea66..a8a96fa9 100644
--- a/src/hir_typeck/expr.hpp
+++ b/src/hir_typeck/expr.hpp
@@ -15,17 +15,6 @@ extern void check_type_class_primitive(const Span& sp, const ::HIR::TypeRef& typ
 
 class TypecheckContext
 {
-    struct IVar
-    {
-        unsigned int alias; // If not ~0, this points to another ivar
-        ::std::unique_ptr< ::HIR::TypeRef> type;    // Type (only nullptr if alias!=0)
-        
-        IVar():
-            alias(~0u),
-            type(new ::HIR::TypeRef())
-        {}
-        bool is_alias() const { return alias != ~0u; }
-    };
     struct Variable
     {
         ::std::string   name;
@@ -46,8 +35,7 @@ public:
     ::std::vector< ::std::pair< const ::HIR::SimplePath*, const ::HIR::Trait* > >   m_traits;
 private:
     ::std::vector< Variable>    m_locals;
-    ::std::vector< IVar>    m_ivars;
-    bool    m_has_changed;
+    HMTypeInferrence    m_ivars;
     
     const ::HIR::GenericParams* m_impl_params;
     const ::HIR::GenericParams* m_item_params;
@@ -55,7 +43,6 @@ private:
 public:
     TypecheckContext(const ::HIR::Crate& crate, const ::HIR::GenericParams* impl_params, const ::HIR::GenericParams* item_params):
         m_crate(crate),
-        m_has_changed(false),
         m_impl_params( impl_params ),
         m_item_params( item_params )
     {
@@ -64,13 +51,10 @@ public:
     void dump() const;
     
     bool take_changed() {
-        bool rv = m_has_changed;
-        m_has_changed = false;
-        return rv;
+        return m_ivars.take_changed();
     }
     void mark_change() {
-        DEBUG("- CHANGE");
-        m_has_changed = true;
+        m_ivars.mark_change();
     }
     
     void push_traits(const ::std::vector<::std::pair< const ::HIR::SimplePath*, const ::HIR::Trait* > >& list);
@@ -171,43 +155,27 @@ public:
             };
     }
     
-    unsigned int new_ivar()
-    {
-        m_ivars.push_back( IVar() );
-        m_ivars.back().type->m_data.as_Infer().index = m_ivars.size() - 1;
-        return m_ivars.size() - 1;
+    unsigned int new_ivar() {
+        return m_ivars.new_ivar();
     }
     ::HIR::TypeRef new_ivar_tr() {
-        ::HIR::TypeRef rv;
-        rv.m_data.as_Infer().index = this->new_ivar();
-        return rv;
+        return m_ivars.new_ivar_tr();
     }
     
-    ::HIR::TypeRef& get_type(::HIR::TypeRef& type)
-    {
-        TU_IFLET(::HIR::TypeRef::Data, type.m_data, Infer, e,
-            assert(e.index != ~0u);
-            return *get_pointed_ivar(e.index).type;
-        )
-        else {
-            return type;
-        }
+    ::HIR::TypeRef& get_type(::HIR::TypeRef& type) {
+        return m_ivars.get_type(type);
     }
-    const ::HIR::TypeRef& get_type(const ::HIR::TypeRef& type) const
-    {
-        TU_IFLET(::HIR::TypeRef::Data, type.m_data, Infer, e,
-            assert(e.index != ~0u);
-            return *get_pointed_ivar(e.index).type;
-        )
-        else {
-            return type;
-        }
+    const ::HIR::TypeRef& get_type(const ::HIR::TypeRef& type) const {
+        return m_ivars.get_type(type);
     }
 
 private:
-    void set_ivar_to(unsigned int slot, ::HIR::TypeRef type);
-    void ivar_unify(unsigned int left_slot, unsigned int right_slot);
-    IVar& get_pointed_ivar(unsigned int slot) const;
+    void set_ivar_to(unsigned int slot, ::HIR::TypeRef type) {
+        m_ivars.set_ivar_to(slot, mv$(type));
+    }
+    void ivar_unify(unsigned int left_slot, unsigned int right_slot) {
+        m_ivars.ivar_unify(left_slot, right_slot);
+    }
 };
 
 }   // namespace typeck
diff --git a/src/hir_typeck/expr_context.cpp b/src/hir_typeck/expr_context.cpp
index be733ddc..9623db6c 100644
--- a/src/hir_typeck/expr_context.cpp
+++ b/src/hir_typeck/expr_context.cpp
@@ -29,18 +29,9 @@ void typeck::TypecheckContext::pop_traits(const ::std::vector<::std::pair< const
 
 void typeck::TypecheckContext::dump() const
 {
-    DEBUG("TypecheckContext - " << m_ivars.size() << " ivars, " << m_locals.size() << " locals");
+    m_ivars.dump();
+    DEBUG("TypecheckContext - " << m_locals.size() << " locals");
     unsigned int i = 0;
-    for(const auto& v : m_ivars) {
-        if(v.is_alias()) {
-            DEBUG("#" << i << " = " << v.alias);
-        }
-        else {
-            DEBUG("#" << i << " = " << *v.type);
-        }
-        i ++ ;
-    }
-    i = 0;
     for(const auto& v : m_locals) {
         DEBUG("VAR " << i << " '"<<v.name<<"' = " << v.type);
         i ++;
@@ -50,7 +41,7 @@ void typeck::TypecheckContext::compact_ivars()
 {
     TRACE_FUNCTION;
     unsigned int i = 0;
-    for(auto& v : m_ivars)
+    for(auto& v : m_ivars.m_ivars)
     {
         if( !v.is_alias() ) {
             auto nt = this->expand_associated_types(Span(), v.type->clone());
@@ -61,11 +52,11 @@ void typeck::TypecheckContext::compact_ivars()
             
             auto index = v.alias;
             unsigned int count = 0;
-            assert(index < m_ivars.size());
-            while( m_ivars.at(index).is_alias() ) {
-                index = m_ivars.at(index).alias;
+            assert(index < m_ivars.m_ivars.size());
+            while( m_ivars.m_ivars.at(index).is_alias() ) {
+                index = m_ivars.m_ivars.at(index).alias;
                 
-                if( count >= m_ivars.size() ) {
+                if( count >= m_ivars.m_ivars.size() ) {
                     this->dump();
                     BUG(Span(), "Loop detected in ivar list when starting at " << v.alias << ", current is " << index);
                 }
@@ -82,28 +73,7 @@ void typeck::TypecheckContext::compact_ivars()
 }
 bool typeck::TypecheckContext::apply_defaults()
 {
-    bool rv = false;
-    for(auto& v : m_ivars)
-    {
-        if( !v.is_alias() ) {
-            TU_IFLET(::HIR::TypeRef::Data, v.type->m_data, Infer, e,
-                switch(e.ty_class)
-                {
-                case ::HIR::InferClass::None:
-                    break;
-                case ::HIR::InferClass::Integer:
-                    rv = true;
-                    *v.type = ::HIR::TypeRef( ::HIR::CoreType::I32 );
-                    break;
-                case ::HIR::InferClass::Float:
-                    rv = true;
-                    *v.type = ::HIR::TypeRef( ::HIR::CoreType::F64 );
-                    break;
-                }
-            )
-        }
-    }
-    return rv;
+    return m_ivars.apply_defaults();
 }
 
 void typeck::TypecheckContext::add_local(unsigned int index, const ::std::string& name, ::HIR::TypeRef type)
@@ -415,7 +385,7 @@ void typeck::TypecheckContext::add_ivars(::HIR::TypeRef& type)
     (Infer,
         if( e.index == ~0u ) {
             e.index = this->new_ivar();
-            this->m_ivars[e.index].type->m_data.as_Infer().ty_class = e.ty_class;
+            this->get_type(type).m_data.as_Infer().ty_class = e.ty_class;
             this->mark_change();
         }
         ),
@@ -2432,104 +2402,3 @@ bool typeck::TypecheckContext::find_field(const Span& sp, const ::HIR::TypeRef&
 }
 
 
-// -------------------------------------------------------------------------------------------------------------------
-//
-// -------------------------------------------------------------------------------------------------------------------
-void typeck::TypecheckContext::set_ivar_to(unsigned int slot, ::HIR::TypeRef type)
-{
-    auto sp = Span();
-    auto& root_ivar = this->get_pointed_ivar(slot);
-    DEBUG("set_ivar_to(" << slot << " { " << *root_ivar.type << " }, " << type << ")");
-    
-    // If the left type was '_', alias the right to it
-    TU_IFLET(::HIR::TypeRef::Data, type.m_data, Infer, l_e,
-        assert( l_e.index != slot );
-        DEBUG("Set IVar " << slot << " = @" << l_e.index);
-        
-        if( l_e.ty_class != ::HIR::InferClass::None ) {
-            TU_MATCH_DEF(::HIR::TypeRef::Data, (root_ivar.type->m_data), (e),
-            (
-                ERROR(sp, E0000, "Type unificiation of literal with invalid type - " << *root_ivar.type);
-                ),
-            (Primitive,
-                check_type_class_primitive(sp, type, l_e.ty_class, e);
-                ),
-            (Infer,
-                // TODO: Check for right having a ty_class
-                if( e.ty_class != ::HIR::InferClass::None && e.ty_class != l_e.ty_class ) {
-                    ERROR(sp, E0000, "Unifying types with mismatching literal classes");
-                }
-                )
-            )
-        }
-        
-        root_ivar.alias = l_e.index;
-        root_ivar.type.reset();
-    )
-    else if( *root_ivar.type == type ) {
-        return ;
-    }
-    else {
-        // Otherwise, store left in right's slot
-        DEBUG("Set IVar " << slot << " = " << type);
-        root_ivar.type = box$( mv$(type) );
-    }
-    
-    this->mark_change();
-}
-
-void typeck::TypecheckContext::ivar_unify(unsigned int left_slot, unsigned int right_slot)
-{
-    auto sp = Span();
-    if( left_slot != right_slot )
-    {
-        auto& left_ivar = this->get_pointed_ivar(left_slot);
-        
-        // TODO: Assert that setting this won't cause a loop.
-        auto& root_ivar = this->get_pointed_ivar(right_slot);
-        
-        TU_IFLET(::HIR::TypeRef::Data, root_ivar.type->m_data, Infer, re,
-            if(re.ty_class != ::HIR::InferClass::None) {
-                TU_MATCH_DEF(::HIR::TypeRef::Data, (left_ivar.type->m_data), (le),
-                (
-                    ERROR(sp, E0000, "Type unificiation of literal with invalid type - " << *left_ivar.type);
-                    ),
-                (Infer,
-                    if( le.ty_class != ::HIR::InferClass::None && le.ty_class != re.ty_class )
-                    {
-                        ERROR(sp, E0000, "Unifying types with mismatching literal classes");
-                    }
-                    le.ty_class = re.ty_class;
-                    ),
-                (Primitive,
-                    check_type_class_primitive(sp, *left_ivar.type, re.ty_class, le);
-                    )
-                )
-            }
-        )
-        else {
-            BUG(sp, "Unifying over a concrete type - " << *root_ivar.type);
-        }
-        
-        root_ivar.alias = left_slot;
-        root_ivar.type.reset();
-        
-        this->mark_change();
-    }
-}
-typeck::TypecheckContext::IVar& typeck::TypecheckContext::get_pointed_ivar(unsigned int slot) const
-{
-    auto index = slot;
-    unsigned int count = 0;
-    assert(index < m_ivars.size());
-    while( m_ivars.at(index).is_alias() ) {
-        index = m_ivars.at(index).alias;
-        
-        if( count >= m_ivars.size() ) {
-            this->dump();
-            BUG(Span(), "Loop detected in ivar list when starting at " << slot << ", current is " << index);
-        }
-        count ++;
-    }
-    return const_cast<IVar&>(m_ivars.at(index));
-}
diff --git a/src/hir_typeck/expr_cs.cpp b/src/hir_typeck/expr_cs.cpp
index 1a1a4751..572c0b63 100644
--- a/src/hir_typeck/expr_cs.cpp
+++ b/src/hir_typeck/expr_cs.cpp
@@ -19,38 +19,34 @@ struct Context
 {
     struct Binding
     {
+        ::std::string   name;
         ::HIR::TypeRef  ty;
-        unsigned int ivar;
-    };
-    struct IVar
-    {
-        //unsigned int    unified_with;
-        ::std::unique_ptr< HIR::TypeRef>    known_type;
+        //unsigned int ivar;
     };
     
     /// Inferrence variable equalities
-    struct TyEq
+    struct Coercion
     {
-        unsigned int left_ivar;
-        unsigned int right_ivar;
-        /// If not nullptr, this points to the node that yeilded `right_ivar` and indicates that a coercion can happen here
-        ::HIR::ExprNodeP* node_ptr_ptr;
+        ::HIR::TypeRef  left_ty;
+        ::HIR::ExprNodeP& right_node_ptr;
     };
-    struct TyConcrete
+    struct Associated
     {
-        unsigned int left_ivar;
-        const ::HIR::TypeRef&   type;
-        ::HIR::ExprNodeP* node_ptr_ptr;
+        ::HIR::TypeRef  left_ty;
+        
+        ::HIR::SimplePath   trait;
+        ::std::vector< ::HIR::TypeRef>  params;
+        ::HIR::TypeRef  impl_ty;
+        const char* name;   // if "", no type is used (and left is ignored) - Just does trait selection
     };
     
     const ::HIR::Crate& m_crate;
     
-    ::std::vector<Binding>  bindings;
-    ::std::vector<IVar> ivars;
+    ::std::vector<Binding>  m_bindings;
+    HMTypeInferrence    m_ivars;
     
-    ::std::vector<TyEq> links;
-    /// Boundary conditions - places where the exact (or partial) type are known
-    ::std::vector<TyConcrete>   boundaries;
+    ::std::vector<Coercion> link_coerce;
+    ::std::vector<Associated> link_assoc;
     /// Nodes that need revisiting (e.g. method calls when the receiver isn't known)
     ::std::vector< ::HIR::ExprNode*>    to_visit;
     
@@ -70,6 +66,8 @@ struct Context
     
     // - Add a pattern binding (forcing the type to match)
     void add_binding(const Span& sp, ::HIR::Pattern& pat, ::HIR::TypeRef& type);
+    
+    void add_var(unsigned int index, const ::std::string& name, ::HIR::TypeRef type);
     const ::HIR::TypeRef& get_var(const Span& sp, unsigned int idx) const;
     
     // - Add a revisit entry
@@ -78,6 +76,11 @@ struct Context
     typedef ::std::vector<::std::pair< const ::HIR::SimplePath*, const ::HIR::Trait* > >    t_trait_list;
     void push_traits(const t_trait_list& list);
     void pop_traits(const t_trait_list& list);
+
+    const ::HIR::TypeRef& get_type(const ::HIR::TypeRef& ty) const { return m_ivars.get_type(ty); }
+    
+private:
+    void add_ivars_params(::HIR::PathParams& params);
 };
 
 //static void fix_param_count(const Span& sp, Context& context, const ::HIR::Path& path, const ::HIR::GenericParams& param_defs,  ::HIR::PathParams& params);
@@ -779,7 +782,7 @@ public:
                 ft.m_arg_types.push_back( monomorphise_type_with(sp, arg.second,  monomorph_cb) );
             auto ty = ::HIR::TypeRef(mv$(ft));
             
-            this->context.apply_equality(node.span(), node.m_res_type, ty);
+            this->context.equate_types(node.span(), node.m_res_type, ty);
             #endif
             )
         )
@@ -825,30 +828,470 @@ void Typecheck_Code_CS(Context context, const ::HIR::TypeRef& result_type, ::HIR
 }
 
 void Context::add_ivars(::HIR::TypeRef& ty) {
+    TU_MATCH(::HIR::TypeRef::Data, (ty.m_data), (e),
+    (Infer,
+        if( e.index == ~0u ) {
+            e.index = this->m_ivars.new_ivar();
+            this->m_ivars.get_type(ty).m_data.as_Infer().ty_class = e.ty_class;
+        }
+        ),
+    (Diverge,
+        ),
+    (Primitive,
+        ),
+    (Path,
+        // Iterate all arguments
+        TU_MATCH(::HIR::Path::Data, (e.path.m_data), (e2),
+        (Generic,
+            this->add_ivars_params(e2.m_params);
+            ),
+        (UfcsKnown,
+            this->add_ivars(*e2.type);
+            this->add_ivars_params(e2.trait.m_params);
+            this->add_ivars_params(e2.params);
+            ),
+        (UfcsUnknown,
+            this->add_ivars(*e2.type);
+            this->add_ivars_params(e2.params);
+            ),
+        (UfcsInherent,
+            this->add_ivars(*e2.type);
+            this->add_ivars_params(e2.params);
+            )
+        )
+        ),
+    (Generic,
+        ),
+    (TraitObject,
+        // Iterate all paths
+        ),
+    (Array,
+        add_ivars(*e.inner);
+        ),
+    (Slice,
+        add_ivars(*e.inner);
+        ),
+    (Tuple,
+        for(auto& ty : e)
+            add_ivars(ty);
+        ),
+    (Borrow,
+        add_ivars(*e.inner);
+        ),
+    (Pointer,
+        add_ivars(*e.inner);
+        ),
+    (Function,
+        // No ivars allowed
+        // TODO: Check?
+        ),
+    (Closure,
+        // Shouldn't be possible
+        )
+    )
 }
-void Context::equate_types(const Span& sp, const ::HIR::TypeRef& l, const ::HIR::TypeRef& r) {
+void Context::add_ivars_params(::HIR::PathParams& params) {
+    for(auto& arg : params.m_types)
+        add_ivars(arg);
 }
-void Context::equate_types_coerce(const Span& sp, const ::HIR::TypeRef& l, ::HIR::ExprNodeP& node_ptr) {
+
+void Context::equate_types(const Span& sp, const ::HIR::TypeRef& li, const ::HIR::TypeRef& ri) {
+    // Instantly apply equality
+    const auto& l_t = this->get_type(li);
+    const auto& r_t = this->get_type(ri);
+    
+    DEBUG("- l_t = " << l_t << ", r_t = " << r_t);
+    TU_IFLET(::HIR::TypeRef::Data, r_t.m_data, Infer, r_e,
+        TU_IFLET(::HIR::TypeRef::Data, l_t.m_data, Infer, l_e,
+            // If both are infer, unify the two ivars (alias right to point to left)
+            this->m_ivars.ivar_unify(l_e.index, r_e.index);
+        )
+        else {
+            // Righthand side is infer, alias it to the left
+            this->m_ivars.set_ivar_to(r_e.index, l_t.clone());
+        }
+    )
+    else {
+        TU_IFLET(::HIR::TypeRef::Data, l_t.m_data, Infer, l_e,
+            // Lefthand side is infer, alias it to the right
+            this->m_ivars.set_ivar_to(l_e.index, r_t.clone());
+        )
+        else {
+        }
+    }
 }
-void Context::add_binding(const Span& sp, ::HIR::Pattern& pat, ::HIR::TypeRef& type) {
+void Context::add_binding(const Span& sp, ::HIR::Pattern& pat, ::HIR::TypeRef& type)
+{
+    TRACE_FUNCTION_F("pat = " << pat << ", type = " << type);
+    
+    if( pat.m_binding.is_valid() ) {
+        const auto& pb = pat.m_binding;
+        
+        assert( pb.is_valid() );
+        switch( pb.m_type )
+        {
+        case ::HIR::PatternBinding::Type::Move:
+            this->add_var( pb.m_slot, pb.m_name, type.clone() );
+            break;
+        case ::HIR::PatternBinding::Type::Ref:
+            this->add_var( pb.m_slot, pb.m_name, ::HIR::TypeRef::new_borrow(::HIR::BorrowType::Shared, type.clone()) );
+            break;
+        case ::HIR::PatternBinding::Type::MutRef:
+            this->add_var( pb.m_slot, pb.m_name, ::HIR::TypeRef::new_borrow(::HIR::BorrowType::Unique, type.clone()) );
+            break;
+        }
+        // TODO: Can there be bindings within a bound pattern?
+        //return ;
+    }
+    
+    // 
+    TU_MATCH(::HIR::Pattern::Data, (pat.m_data), (e),
+    (Any,
+        // Just leave it, the pattern says nothing
+        ),
+    (Value,
+        TODO(sp, "Value pattern");
+        ),
+    (Range,
+        TODO(sp, "Range pattern");
+        ),
+    (Box,
+        TODO(sp, "Box pattern");
+        ),
+    (Ref,
+        if( type.m_data.is_Infer() ) {
+            this->equate_types(sp, type, ::HIR::TypeRef::new_borrow( e.type, this->m_ivars.new_ivar_tr() ));
+            type = this->get_type(type).clone();
+        }
+        // Type must be a &-ptr
+        TU_MATCH_DEF(::HIR::TypeRef::Data, (type.m_data), (te),
+        (
+            ERROR(sp, E0000, "Pattern-type mismatch, expected &-ptr, got " << type);
+            ),
+        (Infer, throw "";),
+        (Borrow,
+            if( te.type != e.type ) {
+                ERROR(sp, E0000, "Pattern-type mismatch, expected &-ptr, got " << type);
+            }
+            this->add_binding(sp, *e.sub, *te.inner );
+            )
+        )
+        ),
+    (Tuple,
+        if( type.m_data.is_Infer() ) {
+            ::std::vector< ::HIR::TypeRef>  sub_types;
+            for(unsigned int i = 0; i < e.sub_patterns.size(); i ++ )
+                sub_types.push_back( this->m_ivars.new_ivar_tr() );
+            this->equate_types(sp, type, ::HIR::TypeRef( mv$(sub_types) ));
+            type = this->get_type(type).clone();
+        }
+        TU_MATCH_DEF(::HIR::TypeRef::Data, (type.m_data), (te),
+        (
+            ERROR(sp, E0000, "Pattern-type mismatch, expected tuple, got " << type);
+            ),
+        (Infer, throw ""; ),
+        (Tuple,
+            if( te.size() != e.sub_patterns.size() ) {
+                ERROR(sp, E0000, "Pattern-type mismatch, expected " << e.sub_patterns.size() << "-tuple, got " << type);
+            }
+            for(unsigned int i = 0; i < e.sub_patterns.size(); i ++ )
+                this->add_binding(sp, e.sub_patterns[i], te[i] );
+            )
+        )
+        ),
+    (Slice,
+        if( type.m_data.is_Infer() ) {
+            this->equate_types(sp, type, ::HIR::TypeRef::new_slice( this->m_ivars.new_ivar_tr() ));
+            type = this->get_type(type).clone();
+        }
+        TU_MATCH_DEF(::HIR::TypeRef::Data, (type.m_data), (te),
+        (
+            ERROR(sp, E0000, "Pattern-type mismatch, expected slice, got " << type);
+            ),
+        (Infer, throw""; ),
+        (Slice,
+            for(auto& sub : e.sub_patterns)
+                this->add_binding(sp, sub, *te.inner );
+            )
+        )
+        ),
+    (SplitSlice,
+        if( type.m_data.is_Infer() ) {
+            this->equate_types(sp, type, ::HIR::TypeRef::new_slice( this->m_ivars.new_ivar_tr() ));
+            type = this->get_type(type).clone();
+        }
+        TU_MATCH_DEF(::HIR::TypeRef::Data, (type.m_data), (te),
+        (
+            ERROR(sp, E0000, "Pattern-type mismatch, expected slice, got " << type);
+            ),
+        (Infer, throw ""; ),
+        (Slice,
+            for(auto& sub : e.leading)
+                this->add_binding( sp, sub, *te.inner );
+            for(auto& sub : e.trailing)
+                this->add_binding( sp, sub, *te.inner );
+            if( e.extra_bind.is_valid() ) {
+                this->add_var( e.extra_bind.m_slot, e.extra_bind.m_name, type.clone() );
+            }
+            )
+        )
+        ),
+    
+    // - Enums/Structs
+    (StructTuple,
+        this->add_ivars_params( e.path.m_params );
+        if( type.m_data.is_Infer() ) {
+            this->equate_types( sp, type, ::HIR::TypeRef::new_path(e.path.clone(), ::HIR::TypeRef::TypePathBinding(e.binding)) );
+            type = this->get_type(type).clone();
+        }
+        assert(e.binding);
+        const auto& str = *e.binding;
+        // - assert check from earlier pass
+        assert( str.m_data.is_Tuple() );
+        const auto& sd = str.m_data.as_Tuple();
+        
+        TU_MATCH_DEF(::HIR::TypeRef::Data, (type.m_data), (te),
+        (
+            ERROR(sp, E0000, "Pattern-type mismatch, expected struct, got " << type);
+            ),
+        (Infer, throw ""; ),
+        (Path,
+            if( ! te.binding.is_Struct() || te.binding.as_Struct() != &str ) {
+                ERROR(sp, E0000, "Type mismatch in struct pattern - " << type << " is not " << e.path);
+            }
+            // NOTE: Must be Generic for the above to have passed
+            auto& gp = te.path.m_data.as_Generic();
+            
+            if( e.sub_patterns.size() != sd.size() ) { 
+                ERROR(sp, E0000, "Tuple struct pattern with an incorrect number of fields");
+            }
+            for( unsigned int i = 0; i < e.sub_patterns.size(); i ++ )
+            {
+                const auto& field_type = sd[i].ent;
+                if( monomorphise_type_needed(field_type) ) {
+                    auto var_ty = monomorphise_type(sp, str.m_params, gp.m_params,  field_type);
+                    this->add_binding(sp, e.sub_patterns[i], var_ty);
+                }
+                else {
+                    // SAFE: Can't have _ as monomorphise_type_needed checks for that
+                    this->add_binding(sp, e.sub_patterns[i], const_cast< ::HIR::TypeRef&>(field_type));
+                }
+            }
+            )
+        )
+        ),
+    (StructTupleWildcard,
+        this->add_ivars_params( e.path.m_params );
+        if( type.m_data.is_Infer() ) {
+            this->equate_types( sp, type, ::HIR::TypeRef::new_path(e.path.clone(), ::HIR::TypeRef::TypePathBinding(e.binding)) );
+            type = this->get_type(type).clone();
+        }
+        assert(e.binding);
+        const auto& str = *e.binding;
+        // - assert check from earlier pass
+        assert( str.m_data.is_Tuple() );
+        
+        TU_MATCH_DEF(::HIR::TypeRef::Data, (type.m_data), (te),
+        (
+            ERROR(sp, E0000, "Type mismatch in struct pattern - " << type << " is not " << e.path);
+            ),
+        (Infer, throw ""; ),
+        (Path,
+            if( ! te.binding.is_Struct() || te.binding.as_Struct() != &str ) {
+                ERROR(sp, E0000, "Type mismatch in struct pattern - " << type << " is not " << e.path);
+            }
+            )
+        )
+        ),
+    (Struct,
+        this->add_ivars_params( e.path.m_params );
+        if( type.m_data.is_Infer() ) {
+            this->equate_types( sp, type, ::HIR::TypeRef::new_path(e.path.clone(), ::HIR::TypeRef::TypePathBinding(e.binding)) );
+            type = this->get_type(type).clone();
+        }
+        assert(e.binding);
+        const auto& str = *e.binding;
+        // - assert check from earlier pass
+        assert( str.m_data.is_Named() );
+        const auto& sd = str.m_data.as_Named();
+        
+        TU_MATCH_DEF(::HIR::TypeRef::Data, (type.m_data), (te),
+        (
+            ERROR(sp, E0000, "Type mismatch in struct pattern - " << type << " is not " << e.path);
+            ),
+        (Infer, throw ""; ),
+        (Path,
+            if( ! te.binding.is_Struct() || te.binding.as_Struct() != &str ) {
+                ERROR(sp, E0000, "Type mismatch in struct pattern - " << type << " is not " << e.path);
+            }
+            // NOTE: Must be Generic for the above to have passed
+            auto& gp = te.path.m_data.as_Generic();
+            for( auto& field_pat : e.sub_patterns )
+            {
+                unsigned int f_idx = ::std::find_if( sd.begin(), sd.end(), [&](const auto& x){ return x.first == field_pat.first; } ) - sd.begin();
+                if( f_idx == sd.size() ) {
+                    ERROR(sp, E0000, "Struct " << e.path << " doesn't have a field " << field_pat.first);
+                }
+                const ::HIR::TypeRef& field_type = sd[f_idx].second.ent;
+                if( monomorphise_type_needed(field_type) ) {
+                    auto field_type_mono = monomorphise_type(sp, str.m_params, gp.m_params,  field_type);
+                    this->add_binding(sp, field_pat.second, field_type_mono);
+                }
+                else {
+                    // SAFE: Can't have _ as monomorphise_type_needed checks for that
+                    this->add_binding(sp, field_pat.second, const_cast< ::HIR::TypeRef&>(field_type));
+                }
+            }
+            )
+        )
+        ),
+    (EnumTuple,
+        this->add_ivars_params( e.path.m_params );
+        if( type.m_data.is_Infer() ) {
+            auto path = e.path.clone();
+            path.m_path.m_components.pop_back();
+
+            this->equate_types( sp, type, ::HIR::TypeRef::new_path(mv$(path), ::HIR::TypeRef::TypePathBinding(e.binding_ptr)) );
+            type = this->get_type(type).clone();
+        }
+        assert(e.binding_ptr);
+        const auto& enm = *e.binding_ptr;
+        const auto& var = enm.m_variants[e.binding_idx].second;
+        assert(var.is_Tuple());
+        const auto& tup_var = var.as_Tuple();
+        
+        TU_MATCH_DEF(::HIR::TypeRef::Data, (type.m_data), (te),
+        (
+            ERROR(sp, E0000, "Type mismatch in enum pattern - " << type << " is not " << e.path);
+            ),
+        (Infer, throw ""; ),
+        (Path,
+            if( ! te.binding.is_Enum() || te.binding.as_Enum() != &enm ) {
+                ERROR(sp, E0000, "Type mismatch in enum pattern - " << type << " is not " << e.path);
+            }
+            // NOTE: Must be Generic for the above to have passed
+            auto& gp = te.path.m_data.as_Generic();
+            if( e.sub_patterns.size() != tup_var.size() ) { 
+                ERROR(sp, E0000, "Enum pattern with an incorrect number of fields - " << e.path << " - expected " << tup_var.size() << ", got " << e.sub_patterns.size());
+            }
+            for( unsigned int i = 0; i < e.sub_patterns.size(); i ++ )
+            {
+                if( monomorphise_type_needed(tup_var[i].ent) ) {
+                    auto var_ty = monomorphise_type(sp, enm.m_params, gp.m_params,  tup_var[i].ent);
+                    this->add_binding(sp, e.sub_patterns[i], var_ty);
+                }
+                else {
+                    // SAFE: Can't have a _ (monomorphise_type_needed checks for that)
+                    this->add_binding(sp, e.sub_patterns[i], const_cast< ::HIR::TypeRef&>(tup_var[i].ent));
+                }
+            }
+            )
+        )
+        ),
+    (EnumTupleWildcard,
+        this->add_ivars_params( e.path.m_params );
+        if( type.m_data.is_Infer() ) {
+            auto path = e.path.clone();
+            path.m_path.m_components.pop_back();
+
+            this->equate_types( sp, type, ::HIR::TypeRef::new_path(mv$(path), ::HIR::TypeRef::TypePathBinding(e.binding_ptr)) );
+            type = this->get_type(type).clone();
+        }
+        assert(e.binding_ptr);
+        const auto& enm = *e.binding_ptr;
+        const auto& var = enm.m_variants[e.binding_idx].second;
+        assert(var.is_Tuple());
+        
+        TU_MATCH_DEF(::HIR::TypeRef::Data, (type.m_data), (te),
+        (
+            ERROR(sp, E0000, "Type mismatch in enum pattern - " << type << " is not " << e.path);
+            ),
+        (Infer, throw ""; ),
+        (Path,
+            if( ! te.binding.is_Enum() || te.binding.as_Enum() != &enm ) {
+                ERROR(sp, E0000, "Type mismatch in enum pattern - " << type << " is not " << e.path);
+            }
+            )
+        )
+        ),
+    (EnumStruct,
+        this->add_ivars_params( e.path.m_params );
+        if( type.m_data.is_Infer() ) {
+            auto path = e.path.clone();
+            path.m_path.m_components.pop_back();
+
+            this->equate_types( sp, type, ::HIR::TypeRef::new_path(mv$(path), ::HIR::TypeRef::TypePathBinding(e.binding_ptr)) );
+            type = this->get_type(type).clone();
+        }
+        assert(e.binding_ptr);
+        const auto& enm = *e.binding_ptr;
+        const auto& var = enm.m_variants[e.binding_idx].second;
+        assert(var.is_Struct());
+        const auto& tup_var = var.as_Struct();
+        
+        TU_MATCH_DEF(::HIR::TypeRef::Data, (type.m_data), (te),
+        (
+            ERROR(sp, E0000, "Type mismatch in enum pattern - " << type << " is not " << e.path);
+            ),
+        (Infer, throw ""; ),
+        (Path,
+            if( ! te.binding.is_Enum() || te.binding.as_Enum() != &enm ) {
+                ERROR(sp, E0000, "Type mismatch in enum pattern - " << type << " is not " << e.path);
+            }
+            // NOTE: Must be Generic for the above to have passed
+            auto& gp = te.path.m_data.as_Generic();
+            
+            for( auto& field_pat : e.sub_patterns )
+            {
+                unsigned int f_idx = ::std::find_if( tup_var.begin(), tup_var.end(), [&](const auto& x){ return x.first == field_pat.first; } ) - tup_var.begin();
+                if( f_idx == tup_var.size() ) {
+                    ERROR(sp, E0000, "Enum variant " << e.path << " doesn't have a field " << field_pat.first);
+                }
+                const ::HIR::TypeRef& field_type = tup_var[f_idx].second.ent;
+                if( monomorphise_type_needed(field_type) ) {
+                    auto field_type_mono = monomorphise_type(sp, enm.m_params, gp.m_params,  field_type);
+                    this->add_binding(sp, field_pat.second, field_type_mono);
+                }
+                else {
+                    // SAFE: Can't have _ as monomorphise_type_needed checks for that
+                    this->add_binding(sp, field_pat.second, const_cast< ::HIR::TypeRef&>(field_type));
+                }
+            }
+            )
+        )
+        )
+    )
 }
+void Context::equate_types_coerce(const Span& sp, const ::HIR::TypeRef& l, ::HIR::ExprNodeP& node_ptr)
+{
+    // - Just record the equality
+}
+void Context::equate_types_assoc(const Span& sp, const ::HIR::TypeRef& l,  const ::HIR::SimplePath& trait, const ::std::vector< ::HIR::TypeRef>& ty_args, const ::HIR::TypeRef& impl_ty, const char *name)
+{
+}
+void Context::add_revisit(::HIR::ExprNode& node) {
+    this->to_visit.push_back( &node );
+}
+
+void Context::add_var(unsigned int index, const ::std::string& name, ::HIR::TypeRef type) {
+    if( m_bindings.size() <= index )
+        m_bindings.resize(index+1);
+    m_bindings[index] = Binding { name, mv$(type) };
+}
+
 const ::HIR::TypeRef& Context::get_var(const Span& sp, unsigned int idx) const {
-    if( idx < this->bindings.size() ) {
-        return this->bindings[idx].ty;
+    if( idx < this->m_bindings.size() ) {
+        return this->m_bindings[idx].ty;
     }
     else {
         BUG(sp, "get_var - Binding index out of range");
     }
 }
-void Context::add_revisit(::HIR::ExprNode& node) {
-}
 void Context::push_traits(const t_trait_list& list) {
 }
 void Context::pop_traits(const t_trait_list& list) {
 }
-void Context::equate_types_assoc(const Span& sp, const ::HIR::TypeRef& l,  const ::HIR::SimplePath& trait, const ::std::vector< ::HIR::TypeRef>& ty_args, const ::HIR::TypeRef& impl_ty, const char *name)
-{
-}
+
 
 template<typename T>
 void fix_param_count_(const Span& sp, Context& context, const T& path, const ::HIR::GenericParams& param_defs,  ::HIR::PathParams& params)
diff --git a/src/hir_typeck/helpers.cpp b/src/hir_typeck/helpers.cpp
index 2829726e..564374b6 100644
--- a/src/hir_typeck/helpers.cpp
+++ b/src/hir_typeck/helpers.cpp
@@ -1,5 +1,7 @@
 
 #include "helpers.hpp"
+#include "expr.hpp"
+
 
 bool monomorphise_type_needed(const ::HIR::TypeRef& tpl);
 
@@ -242,3 +244,308 @@ bool monomorphise_type_needed(const ::HIR::TypeRef& tpl)
         return params.m_types[e.binding];
         }, false);
 }
+
+
+
+void HMTypeInferrence::dump() const
+{
+    unsigned int i = 0;
+    for(const auto& v : m_ivars) {
+        if(v.is_alias()) {
+            DEBUG("#" << i << " = " << v.alias);
+        }
+        else {
+            DEBUG("#" << i << " = " << *v.type);
+        }
+        i ++ ;
+    }
+}
+void HMTypeInferrence::compact_ivars()
+{
+    #if 0
+    unsigned int i = 0;
+    for(auto& v : m_ivars)
+    {
+        if( !v.is_alias() ) {
+            auto nt = this->expand_associated_types(Span(), v.type->clone());
+            DEBUG("- " << i << " " << *v.type << " -> " << nt);
+            *v.type = mv$(nt);
+        }
+        else {
+            
+            auto index = v.alias;
+            unsigned int count = 0;
+            assert(index < m_ivars.size());
+            while( m_ivars.at(index).is_alias() ) {
+                index = m_ivars.at(index).alias;
+                
+                if( count >= m_ivars.size() ) {
+                    this->dump();
+                    BUG(Span(), "Loop detected in ivar list when starting at " << v.alias << ", current is " << index);
+                }
+                count ++;
+            }
+            v.alias = index;
+        }
+        i ++;
+    }
+    #endif
+}
+
+bool HMTypeInferrence::apply_defaults()
+{
+    bool rv = false;
+    for(auto& v : m_ivars)
+    {
+        if( !v.is_alias() ) {
+            TU_IFLET(::HIR::TypeRef::Data, v.type->m_data, Infer, e,
+                switch(e.ty_class)
+                {
+                case ::HIR::InferClass::None:
+                    break;
+                case ::HIR::InferClass::Integer:
+                    rv = true;
+                    *v.type = ::HIR::TypeRef( ::HIR::CoreType::I32 );
+                    break;
+                case ::HIR::InferClass::Float:
+                    rv = true;
+                    *v.type = ::HIR::TypeRef( ::HIR::CoreType::F64 );
+                    break;
+                }
+            )
+        }
+    }
+    return rv;
+}   
+
+void HMTypeInferrence::print_type(::std::ostream& os, const ::HIR::TypeRef& tr) const
+{
+    struct H {
+        static void print_pp(const HMTypeInferrence& ctxt, ::std::ostream& os, const ::HIR::PathParams& pps) {
+            if( pps.m_types.size() > 0 ) {
+                os << "<";
+                for(const auto& pp_t : pps.m_types) {
+                    ctxt.print_type(os, pp_t);
+                    os << ",";
+                }
+                os << ">";
+            }
+        }
+    };
+    const auto& ty = this->get_type(tr);
+    TU_MATCH(::HIR::TypeRef::Data, (ty.m_data), (e),
+    (Infer,
+        os << ty;
+        ),
+    (Primitive,
+        os << ty;
+        ),
+    (Diverge, os << ty; ),
+    (Generic, os << ty; ),
+    (Path,
+        TU_MATCH(::HIR::Path::Data, (e.path.m_data), (pe),
+        (Generic,
+            os << pe.m_path;
+            H::print_pp(*this, os, pe.m_params);
+            ),
+        (UfcsKnown,
+            os << "<";
+            this->print_type(os, *pe.type);
+            os << " as " << pe.trait.m_path;
+            H::print_pp(*this, os, pe.trait.m_params);
+            os << ">::" << pe.item;
+            H::print_pp(*this, os, pe.params);
+            ),
+        (UfcsInherent,
+            os << "<";
+            this->print_type(os, *pe.type);
+            os << ">::" << pe.item;
+            H::print_pp(*this, os, pe.params);
+            ),
+        (UfcsUnknown,
+            BUG(Span(), "UfcsUnknown");
+            )
+        )
+        ),
+    (Borrow,
+        os << "&";
+        this->print_type(os, *e.inner);
+        ),
+    (Pointer,
+        os << "*";
+        this->print_type(os, *e.inner);
+        ),
+    (Slice,
+        os << "[";
+        this->print_type(os, *e.inner);
+        os << "]";
+        ),
+    (Array,
+        os << "[";
+        this->print_type(os, *e.inner);
+        os << "; " << e.size_val << "]";
+        ),
+    (Closure,
+        //for(const auto& arg : e.m_arg_types)
+        //    if( type_contains_ivars(arg) )
+        //        return true;
+        //return type_contains_ivars(*e.m_rettype);
+        ),
+    (Function,
+        //for(const auto& arg : e.m_arg_types)
+        //    if( type_contains_ivars(arg) )
+        //        return true;
+        //return type_contains_ivars(*e.m_rettype);
+        ),
+    (TraitObject,
+        os << "(" << e.m_trait.m_path.m_path;
+        H::print_pp(*this, os, e.m_trait.m_path.m_params);
+        for(const auto& marker : e.m_markers) {
+            os << "+" << marker.m_path;
+            H::print_pp(*this, os, marker.m_params);
+        }
+        os << ")";
+        ),
+    (Tuple,
+        os << "(";
+        for(const auto& st : e) {
+            this->print_type(os, st);
+            os << ",";
+        }
+        os << ")";
+        )
+    )
+}
+unsigned int HMTypeInferrence::new_ivar()
+{
+    m_ivars.push_back( IVar() );
+    m_ivars.back().type->m_data.as_Infer().index = m_ivars.size() - 1;
+    return m_ivars.size() - 1;
+}
+::HIR::TypeRef HMTypeInferrence::new_ivar_tr()
+{
+    ::HIR::TypeRef rv;
+    rv.m_data.as_Infer().index = this->new_ivar();
+    return rv;
+}
+
+::HIR::TypeRef& HMTypeInferrence::get_type(::HIR::TypeRef& type)
+{
+    TU_IFLET(::HIR::TypeRef::Data, type.m_data, Infer, e,
+        assert(e.index != ~0u);
+        return *get_pointed_ivar(e.index).type;
+    )
+    else {
+        return type;
+    }
+}
+
+const ::HIR::TypeRef& HMTypeInferrence::get_type(const ::HIR::TypeRef& type) const
+{
+    TU_IFLET(::HIR::TypeRef::Data, type.m_data, Infer, e,
+        assert(e.index != ~0u);
+        return *get_pointed_ivar(e.index).type;
+    )
+    else {
+        return type;
+    }
+}
+
+void HMTypeInferrence::set_ivar_to(unsigned int slot, ::HIR::TypeRef type)
+{
+    auto sp = Span();
+    auto& root_ivar = this->get_pointed_ivar(slot);
+    DEBUG("set_ivar_to(" << slot << " { " << *root_ivar.type << " }, " << type << ")");
+    
+    // If the left type was '_', alias the right to it
+    TU_IFLET(::HIR::TypeRef::Data, type.m_data, Infer, l_e,
+        assert( l_e.index != slot );
+        DEBUG("Set IVar " << slot << " = @" << l_e.index);
+        
+        if( l_e.ty_class != ::HIR::InferClass::None ) {
+            TU_MATCH_DEF(::HIR::TypeRef::Data, (root_ivar.type->m_data), (e),
+            (
+                ERROR(sp, E0000, "Type unificiation of literal with invalid type - " << *root_ivar.type);
+                ),
+            (Primitive,
+                typeck::check_type_class_primitive(sp, type, l_e.ty_class, e);
+                ),
+            (Infer,
+                // TODO: Check for right having a ty_class
+                if( e.ty_class != ::HIR::InferClass::None && e.ty_class != l_e.ty_class ) {
+                    ERROR(sp, E0000, "Unifying types with mismatching literal classes");
+                }
+                )
+            )
+        }
+        
+        root_ivar.alias = l_e.index;
+        root_ivar.type.reset();
+    )
+    else if( *root_ivar.type == type ) {
+        return ;
+    }
+    else {
+        // Otherwise, store left in right's slot
+        DEBUG("Set IVar " << slot << " = " << type);
+        root_ivar.type = box$( mv$(type) );
+    }
+    
+    //this->mark_change();
+}
+
+void HMTypeInferrence::ivar_unify(unsigned int left_slot, unsigned int right_slot)
+{
+    auto sp = Span();
+    if( left_slot != right_slot )
+    {
+        auto& left_ivar = this->get_pointed_ivar(left_slot);
+        
+        // TODO: Assert that setting this won't cause a loop.
+        auto& root_ivar = this->get_pointed_ivar(right_slot);
+        
+        TU_IFLET(::HIR::TypeRef::Data, root_ivar.type->m_data, Infer, re,
+            if(re.ty_class != ::HIR::InferClass::None) {
+                TU_MATCH_DEF(::HIR::TypeRef::Data, (left_ivar.type->m_data), (le),
+                (
+                    ERROR(sp, E0000, "Type unificiation of literal with invalid type - " << *left_ivar.type);
+                    ),
+                (Infer,
+                    if( le.ty_class != ::HIR::InferClass::None && le.ty_class != re.ty_class )
+                    {
+                        ERROR(sp, E0000, "Unifying types with mismatching literal classes");
+                    }
+                    le.ty_class = re.ty_class;
+                    ),
+                (Primitive,
+                    typeck::check_type_class_primitive(sp, *left_ivar.type, re.ty_class, le);
+                    )
+                )
+            }
+        )
+        else {
+            BUG(sp, "Unifying over a concrete type - " << *root_ivar.type);
+        }
+        
+        root_ivar.alias = left_slot;
+        root_ivar.type.reset();
+        
+        //this->mark_change();
+    }
+}
+HMTypeInferrence::IVar& HMTypeInferrence::get_pointed_ivar(unsigned int slot) const
+{
+    auto index = slot;
+    unsigned int count = 0;
+    assert(index < m_ivars.size());
+    while( m_ivars.at(index).is_alias() ) {
+        index = m_ivars.at(index).alias;
+        
+        if( count >= m_ivars.size() ) {
+            this->dump();
+            BUG(Span(), "Loop detected in ivar list when starting at " << slot << ", current is " << index);
+        }
+        count ++;
+    }
+    return const_cast<IVar&>(m_ivars.at(index));
+}
diff --git a/src/hir_typeck/helpers.hpp b/src/hir_typeck/helpers.hpp
index ea14fd68..866c3645 100644
--- a/src/hir_typeck/helpers.hpp
+++ b/src/hir_typeck/helpers.hpp
@@ -16,3 +16,68 @@ extern ::HIR::GenericPath monomorphise_genericpath_with(const Span& sp, const ::
 extern ::HIR::TraitPath monomorphise_traitpath_with(const Span& sp, const ::HIR::TraitPath& tpl, t_cb_generic callback, bool allow_infer);
 extern ::HIR::TypeRef monomorphise_type_with(const Span& sp, const ::HIR::TypeRef& tpl, t_cb_generic callback, bool allow_infer=true);
 extern ::HIR::TypeRef monomorphise_type(const Span& sp, const ::HIR::GenericParams& params_def, const ::HIR::PathParams& params,  const ::HIR::TypeRef& tpl);
+
+class HMTypeInferrence
+{
+public:
+    struct IVar
+    {
+        unsigned int alias; // If not ~0, this points to another ivar
+        ::std::unique_ptr< ::HIR::TypeRef> type;    // Type (only nullptr if alias!=0)
+        
+        IVar():
+            alias(~0u),
+            type(new ::HIR::TypeRef())
+        {}
+        bool is_alias() const { return alias != ~0u; }
+    };
+    
+    ::std::vector< IVar>    m_ivars;
+    bool    m_has_changed;
+    
+public:
+    HMTypeInferrence():
+        m_has_changed(false)
+    {}
+    
+    bool take_changed() {
+        bool rv = m_has_changed;
+        m_has_changed = false;
+        return rv;
+    }
+    void mark_change() {
+        DEBUG("- CHANGE");
+        m_has_changed = true;
+    }
+    
+    void compact_ivars();
+    void dump() const;
+    bool apply_defaults();
+    
+    void print_type(::std::ostream& os, const ::HIR::TypeRef& tr) const;
+    /// Add (and bind) all '_' types in `type`
+    void add_ivars(::HIR::TypeRef& type);
+    // (helper) Add ivars to path parameters
+    void add_ivars_params(::HIR::PathParams& params);
+    
+    ::std::function<const ::HIR::TypeRef&(const ::HIR::TypeRef&)> callback_resolve_infer() const {
+        return [&](const auto& ty)->const auto& {
+                if( ty.m_data.is_Infer() ) 
+                    return this->get_type(ty);
+                else
+                    return ty;
+            };
+    }
+    
+    unsigned int new_ivar();
+    ::HIR::TypeRef new_ivar_tr();
+    ::HIR::TypeRef& get_type(::HIR::TypeRef& type);
+    const ::HIR::TypeRef& get_type(const ::HIR::TypeRef& type) const;
+    
+    void set_ivar_to(unsigned int slot, ::HIR::TypeRef type);
+    void ivar_unify(unsigned int left_slot, unsigned int right_slot);
+
+private:
+    IVar& get_pointed_ivar(unsigned int slot) const;
+};
+