HIR Typecheck - Fixed associated type lookup

5 files changed, 223 insertions, 204 deletions

diff --git a/Makefile b/Makefile
index d093f4cc..25d53396 100644
--- a/Makefile
+++ b/Makefile
@@ -17,7 +17,7 @@ SHELL = bash
 ifeq ($(DBGTPL),)
   
 else ifeq ($(DBGTPL),gdb)
-  DBG := echo -e "r\nbt 10\nq" | gdb --args
+  DBG := echo -e "r\nbt 12\nq" | gdb --args
 else ifeq ($(DBGTPL),valgrind)
   DBG := valgrind --leak-check=full --num-callers=35
 else
diff --git a/src/hir_typeck/helpers.cpp b/src/hir_typeck/helpers.cpp
index ca30e583..d919bae1 100644
--- a/src/hir_typeck/helpers.cpp
+++ b/src/hir_typeck/helpers.cpp
@@ -1332,202 +1332,8 @@ bool TraitResolution::has_associated_type(const ::HIR::TypeRef& input) const
             // - Only try resolving if the binding isn't known
             if( !e.binding.is_Unbound() )
                 return input;
-            // TODO: If opaque, still search a list of known equalities
-            
-            DEBUG("Locating associated type for " << e.path);
-            
-            *pe.type = expand_associated_types(sp, mv$(*pe.type));
-            
-            
-            // - If it's a closure, then the only trait impls are those generated by typeck
-            TU_IFLET(::HIR::TypeRef::Data, pe.type->m_data, Closure, te,
-                const auto trait_fn = this->m_crate.get_lang_item_path(sp, "fn");
-                const auto trait_fn_mut = this->m_crate.get_lang_item_path(sp, "fn_mut");
-                const auto trait_fn_once = this->m_crate.get_lang_item_path(sp, "fn_once");
-                if( pe.trait.m_path == trait_fn || pe.trait.m_path == trait_fn_mut || pe.trait.m_path == trait_fn_once  ) {
-                    if( pe.item == "Output" ) {
-                        return te.m_rettype->clone();
-                    }
-                    else {
-                        ERROR(sp, E0000, "No associated type " << pe.item << " for trait " << pe.trait);
-                    }
-                }
-                else {
-                    ERROR(sp, E0000, "No implementation of " << pe.trait << " for " << *pe.type);
-                }
-            )
-            
-            //this->find_impl()
-            
-            // 1. Bounds
-            bool rv;
-            bool assume_opaque = true;
-            rv = this->iterate_bounds([&](const auto& b) {
-                TU_MATCH_DEF(::HIR::GenericBound, (b), (be),
-                (
-                    ),
-                (TraitBound,
-                    DEBUG("Trait bound - " << be.type << " : " << be.trait);
-                    // 1. Check if the type matches
-                    //  - TODO: This should be a fuzzier match?
-                    if( be.type != *pe.type )
-                        return false;
-                    // 2. Check if the trait (or any supertrait) includes pe.trait
-                    if( be.trait.m_path == pe.trait ) {
-                        auto it = be.trait.m_type_bounds.find(pe.item);
-                        // 1. Check if the bounds include the desired item
-                        if( it == be.trait.m_type_bounds.end() ) {
-                            // If not, assume it's opaque and return as such
-                            // TODO: What happens if there's two bounds that overlap? 'F: FnMut<()>, F: FnOnce<(), Output=Bar>'
-                            DEBUG("Found impl for " << input << " but no bound on item, assuming opaque");
-                        }
-                        else {
-                            assume_opaque = false;
-                            input = it->second.clone();
-                        }
-                        return true;
-                    }
-                    
-                    bool found_supertrait = this->find_named_trait_in_trait(sp,
-                        pe.trait.m_path, pe.trait.m_params,
-                        *be.trait.m_trait_ptr, be.trait.m_path.m_path, be.trait.m_path.m_params, *pe.type,
-                        [&pe,&input,&assume_opaque](const auto&, const auto& x, const auto& assoc){
-                            auto it = assoc.find(pe.item);
-                            if( it != assoc.end() ) {
-                                assume_opaque = false;
-                                DEBUG("Found associated type " << input << " = " << it->second);
-                                input = it->second.clone();
-                            }
-                            return true;
-                        }
-                        );
-                    if( found_supertrait ) {
-                        auto it = be.trait.m_type_bounds.find(pe.item);
-                        // 1. Check if the bounds include the desired item
-                        if( it == be.trait.m_type_bounds.end() ) {
-                            // If not, assume it's opaque and return as such
-                            // TODO: What happens if there's two bounds that overlap? 'F: FnMut<()>, F: FnOnce<(), Output=Bar>'
-                            if( assume_opaque )
-                                DEBUG("Found impl for " << input << " but no bound on item, assuming opaque");
-                        }
-                        else {
-                            assume_opaque = false;
-                            input = it->second.clone();
-                        }
-                        return true;
-                    }
-                    
-                    // - Didn't match
-                    ),
-                (TypeEquality,
-                    DEBUG("Equality - " << be.type << " = " << be.other_type);
-                    if( input == be.type ) {
-                        assume_opaque = false;
-                        input = be.other_type.clone();
-                        return true;
-                    }
-                    )
-                )
-                return false;
-                });
-            if( rv ) {
-                if( assume_opaque ) {
-                    DEBUG("Assuming that " << input << " is an opaque name");
-                    input.m_data.as_Path().binding = ::HIR::TypeRef::TypePathBinding::make_Opaque({});
-                    
-                    DEBUG("- " << m_type_equalities.size() << " replacements");
-                    for( const auto& v : m_type_equalities )
-                        DEBUG(" > " << v.first << " = " << v.second);
-                    
-                    auto a = m_type_equalities.find(input);
-                    if( a != m_type_equalities.end() ) {
-                        input = a->second.clone();
-                    }
-                }
-                input = this->expand_associated_types(sp, mv$(input));
-                return input;
-            }
-
-            // If the type of this UfcsKnown is ALSO a UfcsKnown - Check if it's bounded by this trait with equality
-            // Use bounds on other associated types too (if `pe.type` was resolved to a fixed associated type)
-            TU_IFLET(::HIR::TypeRef::Data, pe.type->m_data, Path, te_inner,
-                TU_IFLET(::HIR::Path::Data, te_inner.path.m_data, UfcsKnown, pe_inner,
-                    // TODO: Search for equality bounds on this associated type (pe_inner) that match the entire type (pe)
-                    // - Does simplification of complex associated types
-                    const auto& trait_ptr = this->m_crate.get_trait_by_path(sp, pe_inner.trait.m_path);
-                    const auto& assoc_ty = trait_ptr.m_types.at(pe_inner.item);
-                    DEBUG("TODO: Search bounds on associated type - " << assoc_ty.m_trait_bounds);
-                    
-                    // Resolve where Self=pe_inner.type (i.e. for the trait this inner UFCS is on)
-                    auto cb_placeholders_trait = [&](const auto& ty)->const auto&{
-                        TU_IFLET(::HIR::TypeRef::Data, ty.m_data, Generic, e,
-                            if( e.binding == 0xFFFF )
-                                return *pe_inner.type;
-                            else {
-                                // TODO: Look in pe_inner.trait.m_params
-                                TODO(sp, "Handle type params when expanding associated bound (#" << e.binding << " " << e.name);
-                            }
-                        )
-                        else {
-                            return ty;
-                        }
-                        };
-                    for(const auto& bound : assoc_ty.m_trait_bounds)
-                    {
-                        // If the bound is for Self and the outer trait
-                        // - TODO: Parameters?
-                        if( bound.m_path == pe.trait ) {
-                            auto it = bound.m_type_bounds.find( pe.item );
-                            if( it != bound.m_type_bounds.end() ) {
-                                if( monomorphise_type_needed(it->second) ) {
-                                    input = monomorphise_type_with(sp, it->second, cb_placeholders_trait);
-                                }
-                                else {
-                                    input = it->second.clone();
-                                }
-                                input = this->expand_associated_types(sp, mv$(input));
-                                return input;
-                            }
-                        }
-                    }
-                    DEBUG("pe = " << *pe.type << ", input = " << input);
-                )
-            )
-
-            // 2. Crate-level impls
-            // TODO: Search for the actual trait containing this associated type
-            ::HIR::GenericPath  trait_path;
-            if( !this->trait_contains_type(sp, pe.trait, this->m_crate.get_trait_by_path(sp, pe.trait.m_path), pe.item, trait_path) )
-                BUG(sp, "Cannot find associated type " << pe.item << " anywhere in trait " << pe.trait);
-            //pe.trait = mv$(trait_path);
-            
-            DEBUG("Searching for impl");
-            rv = this->find_trait_impls_crate(sp, trait_path.m_path, trait_path.m_params, *pe.type, [&](auto impl, auto qual) {
-                DEBUG("Found " << impl);
-                auto ty = impl.get_type( pe.item.c_str() );
-                if( ty == ::HIR::TypeRef() )
-                    ERROR(sp, E0000, "Couldn't find assocated type " << pe.item << " in " << pe.trait);
-                
-                DEBUG("Converted UfcsKnown - " << e.path << " = " << ty);
-                input = mv$(ty);
-                return true;
-                });
-            if( rv ) {
-                input = this->expand_associated_types(sp, mv$(input));
-                return input;
-            }
-            
-            // If there are no ivars in this path, set its binding to Opaque
-            if( !this->m_ivars.type_contains_ivars(input) ) {
-                // TODO: If the type is a generic or an opaque associated, we can't know.
-                // - If the trait contains any of the above, it's unknowable
-                // - Otherwise, it's an error
-                e.binding = ::HIR::TypeRef::TypePathBinding::make_Opaque({});
-                DEBUG("Couldn't resolve associated type for " << input << " (and won't ever be able to)");
-            }
-            else {
-                DEBUG("Couldn't resolve associated type for " << input << " (will try again later)");
-            }
+            this->expand_associated_types__UfcsKnown(sp, input);
+            return input;
             ),
         (UfcsUnknown,
             BUG(sp, "Encountered UfcsUnknown");
@@ -1567,6 +1373,210 @@ bool TraitResolution::has_associated_type(const ::HIR::TypeRef& input) const
 }
 
 
+void TraitResolution::expand_associated_types__UfcsKnown(const Span& sp, ::HIR::TypeRef& input) const
+{
+    auto& e = input.m_data.as_Path();
+    auto& pe = e.path.m_data.as_UfcsKnown();
+    // TODO: If opaque, still search a list of known equalities
+    
+    DEBUG("Locating associated type for " << e.path);
+    
+    *pe.type = expand_associated_types(sp, mv$(*pe.type));
+    
+    
+    // - If it's a closure, then the only trait impls are those generated by typeck
+    TU_IFLET(::HIR::TypeRef::Data, pe.type->m_data, Closure, te,
+        const auto trait_fn = this->m_crate.get_lang_item_path(sp, "fn");
+        const auto trait_fn_mut = this->m_crate.get_lang_item_path(sp, "fn_mut");
+        const auto trait_fn_once = this->m_crate.get_lang_item_path(sp, "fn_once");
+        if( pe.trait.m_path == trait_fn || pe.trait.m_path == trait_fn_mut || pe.trait.m_path == trait_fn_once  ) {
+            if( pe.item == "Output" ) {
+                input = te.m_rettype->clone();
+                return ;
+            }
+            else {
+                ERROR(sp, E0000, "No associated type " << pe.item << " for trait " << pe.trait);
+            }
+        }
+        else {
+            ERROR(sp, E0000, "No implementation of " << pe.trait << " for " << *pe.type);
+        }
+    )
+    
+    //this->find_impl()
+    
+    // 1. Bounds
+    bool rv;
+    bool assume_opaque = true;
+    rv = this->iterate_bounds([&](const auto& b) {
+        TU_MATCH_DEF(::HIR::GenericBound, (b), (be),
+        (
+            ),
+        (TraitBound,
+            DEBUG("Trait bound - " << be.type << " : " << be.trait);
+            // 1. Check if the type matches
+            //  - TODO: This should be a fuzzier match?
+            if( be.type != *pe.type )
+                return false;
+            // 2. Check if the trait (or any supertrait) includes pe.trait
+            if( be.trait.m_path == pe.trait ) {
+                auto it = be.trait.m_type_bounds.find(pe.item);
+                // 1. Check if the bounds include the desired item
+                if( it == be.trait.m_type_bounds.end() ) {
+                    // If not, assume it's opaque and return as such
+                    // TODO: What happens if there's two bounds that overlap? 'F: FnMut<()>, F: FnOnce<(), Output=Bar>'
+                    DEBUG("Found impl for " << input << " but no bound on item, assuming opaque");
+                }
+                else {
+                    assume_opaque = false;
+                    input = it->second.clone();
+                }
+                return true;
+            }
+            
+            bool found_supertrait = this->find_named_trait_in_trait(sp,
+                pe.trait.m_path, pe.trait.m_params,
+                *be.trait.m_trait_ptr, be.trait.m_path.m_path, be.trait.m_path.m_params, *pe.type,
+                [&pe,&input,&assume_opaque](const auto&, const auto& x, const auto& assoc){
+                    auto it = assoc.find(pe.item);
+                    if( it != assoc.end() ) {
+                        assume_opaque = false;
+                        DEBUG("Found associated type " << input << " = " << it->second);
+                        input = it->second.clone();
+                    }
+                    return true;
+                }
+                );
+            if( found_supertrait ) {
+                auto it = be.trait.m_type_bounds.find(pe.item);
+                // 1. Check if the bounds include the desired item
+                if( it == be.trait.m_type_bounds.end() ) {
+                    // If not, assume it's opaque and return as such
+                    // TODO: What happens if there's two bounds that overlap? 'F: FnMut<()>, F: FnOnce<(), Output=Bar>'
+                    if( assume_opaque )
+                        DEBUG("Found impl for " << input << " but no bound on item, assuming opaque");
+                }
+                else {
+                    assume_opaque = false;
+                    input = it->second.clone();
+                }
+                return true;
+            }
+            
+            // - Didn't match
+            ),
+        (TypeEquality,
+            DEBUG("Equality - " << be.type << " = " << be.other_type);
+            if( input == be.type ) {
+                assume_opaque = false;
+                input = be.other_type.clone();
+                return true;
+            }
+            )
+        )
+        return false;
+        });
+    if( rv ) {
+        if( assume_opaque ) {
+            DEBUG("Assuming that " << input << " is an opaque name");
+            input.m_data.as_Path().binding = ::HIR::TypeRef::TypePathBinding::make_Opaque({});
+            
+            DEBUG("- " << m_type_equalities.size() << " replacements");
+            for( const auto& v : m_type_equalities )
+                DEBUG(" > " << v.first << " = " << v.second);
+            
+            auto a = m_type_equalities.find(input);
+            if( a != m_type_equalities.end() ) {
+                input = a->second.clone();
+            }
+        }
+        input = this->expand_associated_types(sp, mv$(input));
+        return ;
+    }
+
+    // If the type of this UfcsKnown is ALSO a UfcsKnown - Check if it's bounded by this trait with equality
+    // Use bounds on other associated types too (if `pe.type` was resolved to a fixed associated type)
+    TU_IFLET(::HIR::TypeRef::Data, pe.type->m_data, Path, te_inner,
+        TU_IFLET(::HIR::Path::Data, te_inner.path.m_data, UfcsKnown, pe_inner,
+            // TODO: Search for equality bounds on this associated type (pe_inner) that match the entire type (pe)
+            // - Does simplification of complex associated types
+            const auto& trait_ptr = this->m_crate.get_trait_by_path(sp, pe_inner.trait.m_path);
+            const auto& assoc_ty = trait_ptr.m_types.at(pe_inner.item);
+            DEBUG("TODO: Search bounds on associated type - " << assoc_ty.m_trait_bounds);
+            
+            // Resolve where Self=pe_inner.type (i.e. for the trait this inner UFCS is on)
+            auto cb_placeholders_trait = [&](const auto& ty)->const auto&{
+                TU_IFLET(::HIR::TypeRef::Data, ty.m_data, Generic, e,
+                    if( e.binding == 0xFFFF )
+                        return *pe_inner.type;
+                    else {
+                        // TODO: Look in pe_inner.trait.m_params
+                        TODO(sp, "Handle type params when expanding associated bound (#" << e.binding << " " << e.name);
+                    }
+                )
+                else {
+                    return ty;
+                }
+                };
+            for(const auto& bound : assoc_ty.m_trait_bounds)
+            {
+                // If the bound is for Self and the outer trait
+                // - TODO: Parameters?
+                if( bound.m_path == pe.trait ) {
+                    auto it = bound.m_type_bounds.find( pe.item );
+                    if( it != bound.m_type_bounds.end() ) {
+                        if( monomorphise_type_needed(it->second) ) {
+                            input = monomorphise_type_with(sp, it->second, cb_placeholders_trait);
+                        }
+                        else {
+                            input = it->second.clone();
+                        }
+                        input = this->expand_associated_types(sp, mv$(input));
+                        return ;
+                    }
+                }
+            }
+            DEBUG("pe = " << *pe.type << ", input = " << input);
+        )
+    )
+
+    // 2. Crate-level impls
+    // TODO: Search for the actual trait containing this associated type
+    ::HIR::GenericPath  trait_path;
+    if( !this->trait_contains_type(sp, pe.trait, this->m_crate.get_trait_by_path(sp, pe.trait.m_path), pe.item, trait_path) )
+        BUG(sp, "Cannot find associated type " << pe.item << " anywhere in trait " << pe.trait);
+    //pe.trait = mv$(trait_path);
+    
+    DEBUG("Searching for impl");
+    rv = this->find_trait_impls_crate(sp, trait_path.m_path, trait_path.m_params, *pe.type, [&](auto impl, auto qual) {
+        DEBUG("Found " << impl);
+        auto ty = impl.get_type( pe.item.c_str() );
+        if( ty == ::HIR::TypeRef() )
+            ERROR(sp, E0000, "Couldn't find assocated type " << pe.item << " in " << pe.trait);
+        
+        DEBUG("Converted UfcsKnown - " << e.path << " = " << ty);
+        input = mv$(ty);
+        return true;
+        });
+    if( rv ) {
+        input = this->expand_associated_types(sp, mv$(input));
+        return ;
+    }
+    
+    // If there are no ivars in this path, set its binding to Opaque
+    if( !this->m_ivars.type_contains_ivars(input) ) {
+        // TODO: If the type is a generic or an opaque associated, we can't know.
+        // - If the trait contains any of the above, it's unknowable
+        // - Otherwise, it's an error
+        e.binding = ::HIR::TypeRef::TypePathBinding::make_Opaque({});
+        DEBUG("Couldn't resolve associated type for " << input << " (and won't ever be able to)");
+    }
+    else {
+        DEBUG("Couldn't resolve associated type for " << input << " (will try again later)");
+    }
+}
+
+
 // -------------------------------------------------------------------------------------------------------------------
 //
 // -------------------------------------------------------------------------------------------------------------------
@@ -1846,7 +1856,7 @@ bool TraitResolution::find_trait_impls_crate(const Span& sp,
                         ab.second = this->expand_associated_types(sp, mv$(ab.second));
                     }
                     const auto& real_trait_path = real_trait.m_path;
-                    DEBUG("- " << real_type << " : " << real_trait_path);
+                    DEBUG("- " << real_type << " : " << real_trait);
                     auto rv = this->find_trait_impls(sp, real_trait_path.m_path, real_trait_path.m_params, real_type, [&](auto impl, auto impl_cmp) {
                         for(const auto& assoc_bound : real_trait.m_type_bounds) {
                             ::HIR::TypeRef  tmp;
@@ -1904,7 +1914,7 @@ bool TraitResolution::find_trait_impls_crate(const Span& sp,
             //if( match == ::HIR::Compare::Fuzzy ) {
             //    TODO(sp, "- Pass on fuzzy match status");
             //}
-            return callback(ImplRef(mv$(impl_params), impl), match);
+            return callback(ImplRef(mv$(impl_params), impl, mv$(placeholders)), match);
             //return callback(ty_mono, args_mono, types/*, (match == ::HIR::Compare::Fuzzy)*/);
         }
         );
diff --git a/src/hir_typeck/helpers.hpp b/src/hir_typeck/helpers.hpp
index d6b4e149..d5f7e94f 100644
--- a/src/hir_typeck/helpers.hpp
+++ b/src/hir_typeck/helpers.hpp
@@ -167,6 +167,7 @@ public:
     bool has_associated_type(const ::HIR::TypeRef& ty) const;
     /// Expand any located associated types in the input, operating in-place and returning the result
     ::HIR::TypeRef expand_associated_types(const Span& sp, ::HIR::TypeRef input) const;
+    void expand_associated_types__UfcsKnown(const Span& sp, ::HIR::TypeRef& input) const;
     const ::HIR::TypeRef& expand_associated_types(const Span& sp, const ::HIR::TypeRef& input, ::HIR::TypeRef& tmp) const {
         if( this->has_associated_type(input) ) {
             return (tmp = this->expand_associated_types(sp, input.clone()));
diff --git a/src/hir_typeck/impl_ref.hpp b/src/hir_typeck/impl_ref.hpp
index e2ec171e..e98ec988 100644
--- a/src/hir_typeck/impl_ref.hpp
+++ b/src/hir_typeck/impl_ref.hpp
@@ -9,6 +9,7 @@ struct ImplRef
     TAGGED_UNION(Data, TraitImpl,
     (TraitImpl, struct {
         ::std::vector<const ::HIR::TypeRef*>   params;
+        ::std::vector<::HIR::TypeRef>   params_ph;
         const ::HIR::TraitImpl* impl;
         }),
     (BoundedPtr, struct {
@@ -26,10 +27,10 @@ struct ImplRef
     Data    m_data;
     
     ImplRef():
-        m_data(Data::make_TraitImpl({ {}, nullptr }))
+        m_data(Data::make_TraitImpl({ {}, {}, nullptr }))
     {}
-    ImplRef(::std::vector<const ::HIR::TypeRef*> params, const ::HIR::TraitImpl& impl):
-        m_data(Data::make_TraitImpl({ mv$(params), &impl }))
+    ImplRef(::std::vector<const ::HIR::TypeRef*> params, const ::HIR::TraitImpl& impl, ::std::vector< ::HIR::TypeRef> params_ph={}):
+        m_data(Data::make_TraitImpl({ mv$(params), mv$(params_ph), &impl }))
 
     {}
     ImplRef(const ::HIR::TypeRef* type, const ::HIR::PathParams* args, const ::std::map< ::std::string, ::HIR::TypeRef>* assoc):
diff --git a/src/hir_typeck/static.cpp b/src/hir_typeck/static.cpp
index d9972116..7526f76e 100644
--- a/src/hir_typeck/static.cpp
+++ b/src/hir_typeck/static.cpp
@@ -674,8 +674,15 @@ bool ImplRef::type_is_specializable(const char* name) const
                 const auto& ge = gt.m_data.as_Generic();
                 assert(ge.binding < 256);
                 assert(ge.binding < e.params.size());
-                assert(e.params[ge.binding]);
-                return *e.params[ge.binding];
+                if( e.params[ge.binding] ) {
+                    return *e.params[ge.binding];
+                }
+                else if( e.params_ph.size() && e.params_ph[ge.binding] != ::HIR::TypeRef() ) {
+                    return e.params_ph[ge.binding];
+                }
+                else {
+                    BUG(Span(), "Param #" << ge.binding << " " << ge.name << " isn't constrained for " << *this);
+                }
                 };
             return monomorphise_type_with(sp, it->second, cb_monomorph);
         }