HIR Typecheck Static - Fuzzy matched returned (fixes bad From impl selection)

6 files changed, 47 insertions, 34 deletions

diff --git a/src/hir_conv/resolve_ufcs.cpp b/src/hir_conv/resolve_ufcs.cpp
index 13e1da18..671c5be8 100644
--- a/src/hir_conv/resolve_ufcs.cpp
+++ b/src/hir_conv/resolve_ufcs.cpp
@@ -306,15 +306,14 @@ namespace {
             return false;
         }
         
-        bool locate_in_trait_impl_and_set(::HIR::Visitor::PathContext pc, const ::HIR::GenericPath& trait_path, const ::HIR::Trait& trait,  ::HIR::Path::Data& pd) {
-            static Span sp;
-            
+        bool locate_in_trait_impl_and_set(const Span& sp, ::HIR::Visitor::PathContext pc, const ::HIR::GenericPath& trait_path, const ::HIR::Trait& trait,  ::HIR::Path::Data& pd)
+        {
             auto& e = pd.as_UfcsUnknown();
             if( this->locate_item_in_trait(pc, trait,  pd) ) {
                 const auto& type = *e.type;
                 
                 // TODO: This is VERY arbitary and possibly nowhere near what rustc does.
-                this->m_resolve.find_impl(sp,  trait_path.m_path, nullptr, type, [&](const auto& impl){
+                this->m_resolve.find_impl(sp,  trait_path.m_path, nullptr, type, [&](const auto& impl, bool fuzzy){
                     auto pp = impl.get_trait_params();
                     // Replace all placeholder parameters (group 2) with ivars (empty types)
                     pp = monomorphise_path_params_with(sp, pp, [&](const auto& gt)->const auto& {
@@ -325,6 +324,7 @@ namespace {
                         }
                         return gt;
                         }, true);
+                    DEBUG("FOUND impl from " << impl);
                     // If this has already found an option...
                     TU_IFLET( ::HIR::Path::Data, pd, UfcsKnown, e,
                         // Compare all path params, and set different params to _
@@ -345,10 +345,10 @@ namespace {
                         }
                     )
                     else {
+                        DEBUG("pp = " << pp);
                         // Otherwise, set to the current result.
                         pd = get_ufcs_known(mv$(e), ::HIR::GenericPath(trait_path.m_path, mv$(pp)), trait);
                     }
-                    DEBUG("FOUND impl from " << impl);
                     return false;
                     });
                 return pd.is_UfcsKnown();
@@ -365,7 +365,7 @@ namespace {
                 //const auto& par_trait_ent = *trait.m_parent_trait_ptrs[i];
                 const auto& par_trait_ent = m_crate.get_trait_by_path(sp, par_trait_path.m_path);
                 // TODO: Modify path parameters based on the current trait's params
-                if( locate_in_trait_impl_and_set(pc, par_trait_path, par_trait_ent,  pd) ) {
+                if( locate_in_trait_impl_and_set(sp, pc, par_trait_path, par_trait_ent,  pd) ) {
                     return true;
                 }
             }
@@ -404,12 +404,13 @@ namespace {
         
         bool resolve_UfcsUnknown_trait(const ::HIR::Path& p, ::HIR::Visitor::PathContext pc, ::HIR::Path::Data& pd)
         {
+            static Span sp;
             auto& e = pd.as_UfcsUnknown();
             for( const auto& trait_info : m_traits )
             {
                 const auto& trait = *trait_info.second;
                 
-                DEBUG( *trait_info.first << " " << e.item);
+                DEBUG( e.item << " in? " << *trait_info.first );
                 switch(pc)
                 {
                 case ::HIR::Visitor::PathContext::VALUE:
@@ -434,7 +435,7 @@ namespace {
                 // TODO: Search supertraits
                 // TODO: Should impls be searched first, or item names?
                 // - Item names add complexity, but impls are slower
-                if( this->locate_in_trait_impl_and_set(pc, mv$(trait_path), trait,  pd) ) {
+                if( this->locate_in_trait_impl_and_set(sp, pc, mv$(trait_path), trait,  pd) ) {
                     return true;
                 }
             }
@@ -446,7 +447,7 @@ namespace {
             static Span sp;
             
             TU_IFLET(::HIR::Path::Data, p.m_data, UfcsUnknown, e,
-                TRACE_FUNCTION_F("UfcsUnknown - p=" << p);
+                TRACE_FUNCTION_FR("UfcsUnknown - p=" << p, p);
                 
                 this->visit_type( *e.type );
                 this->visit_path_params( e.params );
@@ -557,7 +558,7 @@ namespace {
                     }
                     ),
                 (UfcsKnown,
-                    bool rv = this->m_resolve.find_impl(sp,  pe.trait.m_path, &pe.trait.m_params, *pe.type, [&](const auto& impl) {
+                    bool rv = this->m_resolve.find_impl(sp,  pe.trait.m_path, &pe.trait.m_params, *pe.type, [&](const auto& impl, bool) {
                         if( !impl.m_data.is_TraitImpl() ) {
                             return true;
                         }
diff --git a/src/hir_typeck/expr_check.cpp b/src/hir_typeck/expr_check.cpp
index 6e7ae3f9..e3ec6e51 100644
--- a/src/hir_typeck/expr_check.cpp
+++ b/src/hir_typeck/expr_check.cpp
@@ -768,7 +768,10 @@ namespace {
                 ::HIR::PathParams   params;
                 params.m_types.push_back( ::HIR::TypeRef( mv$(tup_ents) ) );
                 
-                bool found = m_resolve.find_impl(node.span(), trait, &params, val_ty, [](auto ){ return true; });
+                bool found = m_resolve.find_impl(node.span(), trait, &params, val_ty, [&](auto , bool fuzzy){
+                    ASSERT_BUG(node.span(), !fuzzy, "Fuzzy match in check pass");
+                    return true;
+                    });
                 if( !found ) {
                     ERROR(node.span(), E0000, "Unable to find a matching impl of " << trait << " for " << val_ty);
                 }
diff --git a/src/hir_typeck/outer.cpp b/src/hir_typeck/outer.cpp
index ef5e466f..4b4e802d 100644
--- a/src/hir_typeck/outer.cpp
+++ b/src/hir_typeck/outer.cpp
@@ -277,8 +277,10 @@ namespace {
                     }
                     else {
                         ImplRef best_impl;
-                        m_resolve.find_impl(sp, pe.trait.m_path, pe.trait.m_params, *pe.type, [&](auto impl) {
+                        m_resolve.find_impl(sp, pe.trait.m_path, pe.trait.m_params, *pe.type, [&](auto impl, bool fuzzy) {
                             DEBUG("[visit_type] Found " << impl);
+                            if(fuzzy)
+                                TODO(sp, "What error should be used when an impl matches fuzzily in outer?");
                             if( best_impl.more_specific_than(impl) )
                                 return false;
                             best_impl = mv$(impl);
@@ -454,7 +456,7 @@ namespace {
         }
         void visit_path_UfcsUnknown(const Span& sp, ::HIR::Path& p, ::HIR::Visitor::PathContext pc)
         {
-            TRACE_FUNCTION_F("UfcsUnknown - p=" << p);
+            TRACE_FUNCTION_FR("UfcsUnknown - p=" << p, p);
             auto& e = p.m_data.as_UfcsUnknown();
             
             this->visit_type( *e.type );
diff --git a/src/hir_typeck/static.cpp b/src/hir_typeck/static.cpp
index f62c7313..2ce2915b 100644
--- a/src/hir_typeck/static.cpp
+++ b/src/hir_typeck/static.cpp
@@ -98,7 +98,7 @@ bool StaticTraitResolve::find_impl(
     if( !dont_handoff_to_specialised ) {
         if( trait_path == m_lang_Copy ) {
             if( this->type_is_copy(sp, type) ) {
-                return found_cb( ImplRef(&type, &null_params, &null_assoc) );
+                return found_cb( ImplRef(&type, &null_params, &null_assoc), false );
             }
         }
     }
@@ -126,7 +126,7 @@ bool StaticTraitResolve::find_impl(
             }
             ::std::map< ::std::string, ::HIR::TypeRef>  assoc;
             assoc.insert( ::std::make_pair("Output", e.m_rettype->clone()) );
-            return found_cb( ImplRef(type.clone(), trait_params->clone(), mv$(assoc)) );
+            return found_cb( ImplRef(type.clone(), trait_params->clone(), mv$(assoc)), false );
         }
     )
     
@@ -138,7 +138,7 @@ bool StaticTraitResolve::find_impl(
         {
             if( !trait_params || e.m_trait.m_path.m_params == *trait_params )
             {
-                return found_cb( ImplRef(&type, &e.m_trait.m_path.m_params, &e.m_trait.m_type_bounds) );
+                return found_cb( ImplRef(&type, &e.m_trait.m_path.m_params, &e.m_trait.m_type_bounds), false );
             }
         }
         // Markers too
@@ -148,7 +148,7 @@ bool StaticTraitResolve::find_impl(
                 if( !trait_params || mt.m_params == *trait_params )
                 {
                     static ::std::map< ::std::string, ::HIR::TypeRef>  types;
-                    return found_cb( ImplRef(&type, &mt.m_params, &types) );
+                    return found_cb( ImplRef(&type, &mt.m_params, &types), false );
                 }
             }
         }
@@ -167,7 +167,7 @@ bool StaticTraitResolve::find_impl(
                     assoc_clone.insert( ::std::make_pair(e2.first, e2.second.clone()) );
                 auto ir = ImplRef(type.clone(), i_params.clone(), mv$(assoc_clone));
                 DEBUG("- ir = " << ir);
-                rv = found_cb( mv$(ir) );
+                rv = found_cb( mv$(ir), false );
                 return false;
             });
         if( is_supertrait )
@@ -205,13 +205,13 @@ bool StaticTraitResolve::find_impl(
                     {
                         if( &b_params_mono == &params_mono_o )
                         {
-                            if( found_cb( ImplRef(type.clone(), mv$(params_mono_o), {}) ) )
+                            if( found_cb( ImplRef(type.clone(), mv$(params_mono_o), {}), false ) )
                                 return true;
                             params_mono_o = monomorphise_path_params_with(sp, b_params, monomorph_cb, false);
                         }
                         else
                         {
-                            if( found_cb( ImplRef(&type, &bound.m_path.m_params, &null_assoc) ) )
+                            if( found_cb( ImplRef(&type, &bound.m_path.m_params, &null_assoc), false ) )
                                 return true;
                         }
                     }
@@ -222,7 +222,7 @@ bool StaticTraitResolve::find_impl(
                         if( i_params != *trait_params )
                             return false;
                         DEBUG("impl " << trait_path << i_params << " for " << type << " -- desired " << trait_path << *trait_params);
-                        return found_cb( ImplRef(type.clone(), i_params.clone(), {}) );
+                        return found_cb( ImplRef(type.clone(), i_params.clone(), {}), false );
                     });
                 if( ret )
                     return true;
@@ -297,7 +297,7 @@ bool StaticTraitResolve::find_impl__check_bound(
                     return false;
             }
             // Hand off to the closure, and return true if it does
-            if( found_cb(ImplRef(&e.type, &e.trait.m_path.m_params, &e.trait.m_type_bounds)) ) {
+            if( found_cb(ImplRef(&e.type, &e.trait.m_path.m_params, &e.trait.m_type_bounds), false) ) {
                 return true;
             }
         }
@@ -314,7 +314,7 @@ bool StaticTraitResolve::find_impl__check_bound(
                         assoc.insert( ::std::make_pair(i.first, i.second.clone())  );
                     //}
                 }
-                return found_cb( ImplRef(type.clone(), params.clone(), mv$(assoc)) );
+                return found_cb( ImplRef(type.clone(), params.clone(), mv$(assoc)), false );
             });
         if( rv ) {
             return true;
@@ -348,7 +348,7 @@ bool StaticTraitResolve::find_impl__check_bound(
                 }
                 DEBUG("- tp_mono = " << tp_mono);
                 // TODO: Instead of using `type` here, build the real type
-                if( found_cb( ImplRef(type.clone(), mv$(tp_mono.m_path.m_params), mv$(tp_mono.m_type_bounds)) ) ) {
+                if( found_cb( ImplRef(type.clone(), mv$(tp_mono.m_path.m_params), mv$(tp_mono.m_type_bounds)), false ) ) {
                     return true;
                 }
             }
@@ -393,9 +393,8 @@ bool StaticTraitResolve::find_impl__check_crate(
             match &= l.match_test_generics_fuzz(sp, r, cb_ident, cb);
         }
     }
-    if( match != ::HIR::Compare::Equal ) {
+    if( match == ::HIR::Compare::Unequal ) {
         DEBUG(" > Type mismatch");
-        // TODO: Support fuzzy matches for some edge cases. E.g. in parts of outer typecheck?
         return false;
     }
     
@@ -477,7 +476,7 @@ bool StaticTraitResolve::find_impl__check_crate(
                         rv = true;
                     }
                     else {
-                        rv = this->find_impl(sp, aty_src_trait.m_path, aty_src_trait.m_params, b_ty_mono, [&](const auto& impl) {
+                        rv = this->find_impl(sp, aty_src_trait.m_path, aty_src_trait.m_params, b_ty_mono, [&](const auto& impl, bool) {
                             ::HIR::TypeRef have = impl.get_type(aty_name.c_str());
                             this->expand_associated_types(sp, have);
                             
@@ -499,7 +498,11 @@ bool StaticTraitResolve::find_impl__check_crate(
                 rv = true;
             }
             else {
-                rv = this->find_impl(sp, b_tp_mono.m_path.m_path, b_tp_mono.m_path.m_params, b_ty_mono, [&](const auto& impl) {
+                rv = this->find_impl(sp, b_tp_mono.m_path.m_path, b_tp_mono.m_path.m_params, b_ty_mono, [&](const auto& impl, bool) {
+                    //if( fuzzy ) {
+                    //    DEBUG("[find_impl__check_bound] - Fuzzy in bound");
+                    //    return false;
+                    //}
                     
                     #if 0
                     for(const auto& assoc_bound : b_tp_mono.m_type_bounds) {
@@ -529,7 +532,7 @@ bool StaticTraitResolve::find_impl__check_crate(
         )
     }
     
-    return found_cb( ImplRef(impl_params, trait_path, impl, mv$(placeholders)) );
+    return found_cb( ImplRef(impl_params, trait_path, impl, mv$(placeholders)), (match == ::HIR::Compare::Fuzzy) );
 }
 
 void StaticTraitResolve::expand_associated_types(const Span& sp, ::HIR::TypeRef& input) const
@@ -791,8 +794,12 @@ void StaticTraitResolve::expand_associated_types__UfcsKnown(const Span& sp, ::HI
     //e2.trait = mv$(trait_path);
     
     ::ImplRef  best_impl;
-    rv = this->find_impl(sp, trait_path.m_path, trait_path.m_params, *e2.type, [&](auto impl) {
+    rv = this->find_impl(sp, trait_path.m_path, trait_path.m_params, *e2.type, [&](auto impl, bool fuzzy) {
         DEBUG("[expand_associated_types] Found " << impl);
+        if( fuzzy ) {
+            DEBUG("[expand_associated_types] - Fuzzy");
+            return false;
+        }
         
         if( impl.type_is_specialisable(e2.item.c_str()) ) {
             if( impl.more_specific_than(best_impl) ) {
@@ -951,12 +958,12 @@ bool StaticTraitResolve::type_is_copy(const Span& sp, const ::HIR::TypeRef& ty)
     (Generic,
         return this->iterate_bounds([&](const auto& b) {
             auto pp = ::HIR::PathParams();
-            return this->find_impl__check_bound(sp, m_lang_Copy, &pp, ty, [&](auto ){ return true; },  b);
+            return this->find_impl__check_bound(sp, m_lang_Copy, &pp, ty, [&](auto , bool ){ return true; },  b);
             });
         ),
     (Path,
         auto pp = ::HIR::PathParams();
-        return this->find_impl(sp, m_lang_Copy, &pp, ty, [&](auto ){ return true; }, true);
+        return this->find_impl(sp, m_lang_Copy, &pp, ty, [&](auto , bool){ return true; }, true);
         ),
     (Diverge,
         // The ! type is kinda Copy ...
diff --git a/src/hir_typeck/static.hpp b/src/hir_typeck/static.hpp
index c6a37c3a..dd8031de 100644
--- a/src/hir_typeck/static.hpp
+++ b/src/hir_typeck/static.hpp
@@ -87,7 +87,7 @@ public:
     
     /// \brief Lookups
     /// \{
-    typedef ::std::function<bool(ImplRef)> t_cb_find_impl;
+    typedef ::std::function<bool(ImplRef, bool is_fuzzed)> t_cb_find_impl;
     
     bool find_impl(
         const Span& sp,
diff --git a/src/mir/from_hir.cpp b/src/mir/from_hir.cpp
index 1c3bddb4..670acf24 100644
--- a/src/mir/from_hir.cpp
+++ b/src/mir/from_hir.cpp
@@ -1029,7 +1029,7 @@ namespace {
                 TU_MATCH_DEF( ::HIR::TypeRef::Data, (ty_out.m_data), (e),
                 (
                     const auto& lang_Unsize = m_builder.crate().get_lang_item_path(node.span(), "unsize");
-                    if( m_builder.resolve().find_impl( node.span(), lang_Unsize, ::HIR::PathParams(ty_out.clone()), ty_in.clone(), [](auto ){ return true; }) )
+                    if( m_builder.resolve().find_impl( node.span(), lang_Unsize, ::HIR::PathParams(ty_out.clone()), ty_in.clone(), [](auto , bool ){ return true; }) )
                     {
                         // - HACK: Emit a cast operation on the pointers. Leave it up to monomorph to 'fix' it
                         m_builder.set_result( node.span(), ::MIR::RValue::make_Cast({ mv$(ptr_lval), node.m_res_type.clone() }) );