Resolve UFCS - Move all "Outer" logic to resolve_ufcs.cpp, and switch to using that instead (also includes changes to align the two files)

4 files changed, 122 insertions, 58 deletions

diff --git a/src/hir_conv/main_bindings.hpp b/src/hir_conv/main_bindings.hpp
index a7bc9de6..41da7c46 100644
--- a/src/hir_conv/main_bindings.hpp
+++ b/src/hir_conv/main_bindings.hpp
@@ -15,6 +15,7 @@ namespace HIR {
 
 extern void ConvertHIR_ExpandAliases(::HIR::Crate& crate);
 extern void ConvertHIR_Bind(::HIR::Crate& crate);
+extern void ConvertHIR_ResolveUFCS_SortImpls(::HIR::Crate& crate);
 extern void ConvertHIR_ResolveUFCS_Outer(::HIR::Crate& crate);
 extern void ConvertHIR_ResolveUFCS(::HIR::Crate& crate);
 extern void ConvertHIR_Markings(::HIR::Crate& crate);
diff --git a/src/hir_conv/resolve_ufcs.cpp b/src/hir_conv/resolve_ufcs.cpp
index 470e26fb..68f3ec64 100644
--- a/src/hir_conv/resolve_ufcs.cpp
+++ b/src/hir_conv/resolve_ufcs.cpp
@@ -15,12 +15,14 @@
 #include <hir/expr.hpp>
 #include <hir/visitor.hpp>
 #include <hir_typeck/static.hpp>
+#include <algorithm>    // std::remove_if
 
 namespace {
     class Visitor:
         public ::HIR::Visitor
     {
         const ::HIR::Crate& m_crate;
+        bool m_visit_exprs;
 
         typedef ::std::vector< ::std::pair< const ::HIR::SimplePath*, const ::HIR::Trait* > >   t_trait_imports;
         t_trait_imports m_traits;
@@ -28,12 +30,13 @@ namespace {
         StaticTraitResolve  m_resolve;
         const ::HIR::TypeRef* m_current_type = nullptr;
         const ::HIR::Trait* m_current_trait = nullptr;
-        const ::HIR::ItemPath* m_current_trait_path;
+        const ::HIR::ItemPath* m_current_trait_path = nullptr;
         bool m_in_expr = false;
 
     public:
-        Visitor(const ::HIR::Crate& crate):
+        Visitor(const ::HIR::Crate& crate, bool visit_exprs):
             m_crate(crate),
+            m_visit_exprs(visit_exprs),
             m_resolve(crate)
         {}
 
@@ -228,7 +231,7 @@ namespace {
                 }
             };
 
-            if( expr.get() != nullptr )
+            if( m_visit_exprs &&  expr.get() != nullptr )
             {
                 m_in_expr = true;
                 ExprVisitor v { *this };
@@ -523,13 +526,16 @@ namespace {
 
             // TODO: If this an associated type, check for default trait params
 
-            unsigned counter = 0;
-            while( m_resolve.expand_associated_types_single(sp, ty) )
+            if( m_visit_exprs )
             {
-                ASSERT_BUG(sp, counter++ < 20, "Sanity limit exceeded when resolving UFCS in type " << ty);
-                // Invoke a special version of EAT that only processes a single item.
-                // - Keep recursing while this does replacements
-                ::HIR::Visitor::visit_type(ty);
+                unsigned counter = 0;
+                while( m_resolve.expand_associated_types_single(sp, ty) )
+                {
+                    ASSERT_BUG(sp, counter++ < 20, "Sanity limit exceeded when resolving UFCS in type " << ty);
+                    // Invoke a special version of EAT that only processes a single item.
+                    // - Keep recursing while this does replacements
+                    ::HIR::Visitor::visit_type(ty);
+                }
             }
         }
 
@@ -558,7 +564,8 @@ namespace {
                 this->visit_type( *e.type );
                 this->visit_path_params( e.params );
 
-                // Self resolves from the current trait before looking for bounds
+                // If processing a trait, and the type is 'Self', search for the type/method on the trait
+                // - Explicitly encoded because `Self::Type` has a different meaning to `MyType::Type` (the latter will search bounds first)
                 if( *e.type == ::HIR::TypeRef("Self", 0xFFFF) )
                 {
                     ::HIR::GenericPath  trait_path;
@@ -604,6 +611,7 @@ namespace {
                 assert(p.m_data.is_UfcsUnknown());
 
                 // If the type is the impl type, look for items AFTER generic lookup
+                // TODO: Should this look up in-scope traits instead of hard-coding this hack?
                 if( m_current_type && *e.type == *m_current_type )
                 {
                     ::HIR::GenericPath  trait_path;
@@ -640,7 +648,8 @@ namespace {
                 // Couldn't find it
                 ERROR(sp, E0000, "Failed to find impl with '" << e.item << "' for " << *e.type << " (in " << p << ")");
             }
-            else {
+            else
+            {
                 ::HIR::Visitor::visit_path(p, pc);
             }
         }
@@ -708,10 +717,53 @@ namespace {
         }
     };
 
-}
+    template<typename T>
+    void sort_impl_group(::HIR::Crate::ImplGroup<T>& ig)
+    {
+        auto new_end = ::std::remove_if(ig.generic.begin(), ig.generic.end(), [&ig](::std::unique_ptr<T>& ty_impl) {
+            const auto& type = ty_impl->m_type;  // Using field accesses in templates feels so dirty
+            const ::HIR::SimplePath*    path = type.get_sort_path();
+
+            if( path )
+            {
+                ig.named[*path].push_back(mv$(ty_impl));
+            }
+            else if( type.m_data.is_Path() || type.m_data.is_Generic() )
+            {
+                return false;
+            }
+            else
+            {
+                ig.non_named.push_back(mv$(ty_impl));
+            }
+            return true;
+            });
+        ig.generic.erase(new_end, ig.generic.end());
+    }
+}   // namespace ""
 
+void ConvertHIR_ResolveUFCS_Outer(::HIR::Crate& crate)
+{
+    Visitor exp { crate, false };
+    exp.visit_crate( crate );
+}
 void ConvertHIR_ResolveUFCS(::HIR::Crate& crate)
 {
-    Visitor exp { crate };
+    Visitor exp { crate, true };
     exp.visit_crate( crate );
 }
+
+void ConvertHIR_ResolveUFCS_SortImpls(::HIR::Crate& crate)
+{
+    // Sort impls!
+    sort_impl_group(crate.m_type_impls);
+    DEBUG("Type impl counts: " << crate.m_type_impls.named.size() << " path groups, " << crate.m_type_impls.non_named.size() << " primitive, " << crate.m_type_impls.generic.size() << " ungrouped");
+    for(auto& impl_group : crate.m_trait_impls)
+    {
+        sort_impl_group(impl_group.second);
+    }
+    for(auto& impl_group : crate.m_marker_impls)
+    {
+        sort_impl_group(impl_group.second);
+    }
+}
diff --git a/src/hir_conv/resolve_ufcs_outer.cpp b/src/hir_conv/resolve_ufcs_outer.cpp
index 4baf86a2..c4ab373a 100644
--- a/src/hir_conv/resolve_ufcs_outer.cpp
+++ b/src/hir_conv/resolve_ufcs_outer.cpp
@@ -12,6 +12,7 @@
 #include <hir/hir.hpp>
 #include <hir/expr.hpp>
 #include <hir/visitor.hpp>
+#include <hir_typeck/static.hpp>
 #include <hir_typeck/common.hpp>    // monomorphise_genericpath_needed
 #include <algorithm>
 
@@ -21,32 +22,28 @@ namespace {
     {
         const ::HIR::Crate& m_crate;
 
-        const ::HIR::GenericParams*   m_params_impl = nullptr;
-        const ::HIR::GenericParams*   m_params_method = nullptr;
-
-        const ::HIR::TypeRef* m_current_type = nullptr; // used because sometimes `Self` is already replaced
+        StaticTraitResolve  m_resolve;
+        const ::HIR::TypeRef* m_current_type = nullptr; // used because sometimes `Self` is encoded expanded (is this a problem?)
         const ::HIR::Trait* m_current_trait = nullptr;
         const ::HIR::ItemPath* m_current_trait_path = nullptr;
 
     public:
         Visitor(const ::HIR::Crate& crate):
-            m_crate(crate)
+            m_crate(crate),
+            m_resolve(crate)
         {}
 
         void visit_struct(::HIR::ItemPath p, ::HIR::Struct& item) override {
-            m_params_method = &item.m_params;
+            auto _ = m_resolve.set_item_generics(item.m_params);
             ::HIR::Visitor::visit_struct(p, item);
-            m_params_method = nullptr;
         }
         void visit_enum(::HIR::ItemPath p, ::HIR::Enum& item) override {
-            m_params_method = &item.m_params;
+            auto _ = m_resolve.set_item_generics(item.m_params);
             ::HIR::Visitor::visit_enum(p, item);
-            m_params_method = nullptr;
         }
         void visit_function(::HIR::ItemPath p, ::HIR::Function& item) override {
-            m_params_method = &item.m_params;
+            auto _ = m_resolve.set_item_generics(item.m_params);
             ::HIR::Visitor::visit_function(p, item);
-            m_params_method = nullptr;
         }
         void visit_type_alias(::HIR::ItemPath p, ::HIR::TypeAlias& item) override {
             // NOTE: Disabled, becuase generics in type aliases are never checked
@@ -56,26 +53,24 @@ namespace {
 #endif
         }
         void visit_trait(::HIR::ItemPath p, ::HIR::Trait& trait) override {
-            m_params_impl = &trait.m_params;
             m_current_trait = &trait;
             m_current_trait_path = &p;
+            auto _ = m_resolve.set_impl_generics(trait.m_params);
             ::HIR::Visitor::visit_trait(p, trait);
             m_current_trait = nullptr;
-            m_params_impl = nullptr;
         }
         void visit_type_impl(::HIR::TypeImpl& impl) override {
             TRACE_FUNCTION_F("impl" << impl.m_params.fmt_args() << " " << impl.m_type << " (mod=" << impl.m_src_module << ")");
-            m_params_impl = &impl.m_params;
+            auto _g = m_resolve.set_impl_generics(impl.m_params);
             m_current_type = &impl.m_type;
             ::HIR::Visitor::visit_type_impl(impl);
             m_current_type = nullptr;
-            m_params_impl = nullptr;
         }
         void visit_marker_impl(const ::HIR::SimplePath& trait_path, ::HIR::MarkerImpl& impl) override {
             ::HIR::ItemPath    p( impl.m_type, trait_path, impl.m_trait_args );
             TRACE_FUNCTION_F("impl" << impl.m_params.fmt_args() << " " << trait_path << impl.m_trait_args << " for " << impl.m_type << " (mod=" << impl.m_src_module << ")");
 
-            m_params_impl = &impl.m_params;
+            auto _g = m_resolve.set_impl_generics(impl.m_params);
             m_current_type = &impl.m_type;
             m_current_trait = &m_crate.get_trait_by_path(Span(), trait_path);
             m_current_trait_path = &p;
@@ -84,13 +79,12 @@ namespace {
 
             m_current_trait = nullptr;
             m_current_type = nullptr;
-            m_params_impl = nullptr;
         }
         void visit_trait_impl(const ::HIR::SimplePath& trait_path, ::HIR::TraitImpl& impl) override {
             ::HIR::ItemPath    p( impl.m_type, trait_path, impl.m_trait_args );
             TRACE_FUNCTION_F("impl" << impl.m_params.fmt_args() << " " << trait_path << impl.m_trait_args << " for " << impl.m_type << " (mod=" << impl.m_src_module << ")");
 
-            m_params_impl = &impl.m_params;
+            auto _g = m_resolve.set_impl_generics(impl.m_params);
             m_current_type = &impl.m_type;
             m_current_trait = &m_crate.get_trait_by_path(Span(), trait_path);
             m_current_trait_path = &p;
@@ -99,7 +93,6 @@ namespace {
 
             m_current_trait = nullptr;
             m_current_type = nullptr;
-            m_params_impl = nullptr;
         }
 
         void visit_expr(::HIR::ExprPtr& expr) override
@@ -356,6 +349,30 @@ namespace {
                 });
         }
 
+
+        void visit_type(::HIR::TypeRef& ty) override
+        {
+#if 0
+            // TODO: Add a span parameter.
+            static Span sp;
+#endif
+
+            ::HIR::Visitor::visit_type(ty);
+
+#if 0
+            // TODO: If this an associated type, check for default trait params
+
+            unsigned counter = 0;
+            while( m_resolve.expand_associated_types_single(sp, ty) )
+            {
+                ASSERT_BUG(sp, counter++ < 20, "Sanity limit exceeded when resolving UFCS in type " << ty);
+                // Invoke a special version of EAT that only processes a single item.
+                // - Keep recursing while this does replacements
+                ::HIR::Visitor::visit_type(ty);
+            }
+#endif
+        }
+
         void visit_path(::HIR::Path& p, ::HIR::Visitor::PathContext pc) override
         {
             static Span sp;
@@ -370,8 +387,7 @@ namespace {
                 this->visit_path_params( e.params );
 
                 // If processing a trait, and the type is 'Self', search for the type/method on the trait
-                // - TODO: This could be encoded by a `Self: Trait` bound in the generics, but that may have knock-on issues?
-                // NOTE: `Self` can already be replaced by the self type (AST resolve does this)
+                // - Explicitly encoded because `Self::Type` has a different meaning to `MyType::Type` (the latter will search bounds first)
                 if( *e.type == ::HIR::TypeRef("Self", 0xFFFF) )
                 {
                     ::HIR::GenericPath  trait_path;
@@ -395,15 +411,18 @@ namespace {
                 }
 
                 // Search for matching impls in current generic blocks
-                if( m_params_method != nullptr && locate_trait_item_in_bounds(pc, *e.type, *m_params_method,  p.m_data) ) {
+                if( m_resolve.m_item_generics != nullptr && locate_trait_item_in_bounds(pc, *e.type, *m_resolve.m_item_generics,  p.m_data) ) {
                     DEBUG("Found in item params, p = " << p);
                     return ;
                 }
-                if( m_params_impl != nullptr && locate_trait_item_in_bounds(pc, *e.type, *m_params_impl,  p.m_data) ) {
+                if( m_resolve.m_impl_generics != nullptr && locate_trait_item_in_bounds(pc, *e.type, *m_resolve.m_impl_generics,  p.m_data) ) {
                     DEBUG("Found in impl params, p = " << p);
                     return ;
                 }
 
+
+                // If the type is the impl type, look for items AFTER generic lookup
+                // TODO: Should this look up in-scope traits instead of hard-coding this hack?
                 if( m_current_type && *e.type == *m_current_type )
                 {
                     ::HIR::GenericPath  trait_path;
@@ -426,24 +445,14 @@ namespace {
                     DEBUG("- Item " << e.item << " not found in Self - ty=" << *e.type);
                 }
 
-                // Cases for the type:
-                // - Path:UfcsKnown - Search trait impl's ATY bounds (and our own bound set?)
-                // - Generic - Search local bound set for a suitable implemented trait
-                // - Anything else - ERROR
-                if( e.type->m_data.is_Path() && e.type->m_data.as_Path().path.m_data.is_UfcsKnown() )
-                {
-                    // TODO: Search bounds on this ATY (in the trait defintiion)
-                    TODO(sp, "Get " << e.item << " for " << *e.type);
-                }
-                else if( e.type->m_data.is_Generic())
-                {
-                    // Local bounds have already been searched, error now?
-                    TODO(sp, "Get " << e.item << " for " << *e.type);
-                }
-                else
-                {
-                    ERROR(sp, E0000, "Ambigious associated type " << p);    // rustc E0223
-                }
+                // TODO: Search all impls of in-scope traits for this method on this type?
+                //if( this->resolve_UfcsUnknown_trait(p, pc, p.m_data) ) {
+                //    return ;
+                //}
+                assert(p.m_data.is_UfcsUnknown());
+
+                // Couldn't find it
+                ERROR(sp, E0000, "Failed to find impl with '" << e.item << "' for " << *e.type << " (in " << p << ")");
             }
             else
             {
@@ -452,9 +461,6 @@ namespace {
         }
     };
 
-}
-
-namespace {
     template<typename T>
     void sort_impl_group(::HIR::Crate::ImplGroup<T>& ig)
     {
@@ -478,8 +484,9 @@ namespace {
             });
         ig.generic.erase(new_end, ig.generic.end());
     }
-}
+}   // namespace ""
 
+#if 0
 void ConvertHIR_ResolveUFCS_Outer(::HIR::Crate& crate)
 {
     Visitor exp { crate };
@@ -497,3 +504,4 @@ void ConvertHIR_ResolveUFCS_Outer(::HIR::Crate& crate)
         sort_impl_group(impl_group.second);
     }
 }
+#endif
\ No newline at end of file
diff --git a/src/main.cpp b/src/main.cpp
index 0002e1a8..83ddc4c1 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -517,6 +517,9 @@ int main(int argc, char *argv[])
         CompilePhaseV("Resolve HIR Markings", [&]() {
             ConvertHIR_Markings(*hir_crate);
             });
+        CompilePhaseV("Sort Impls", [&]() {
+            ConvertHIR_ResolveUFCS_SortImpls(*hir_crate);
+            });
         // Determine what trait to use for <T>::Foo in outer scope
         CompilePhaseV("Resolve UFCS Outer", [&]() {
             ConvertHIR_ResolveUFCS_Outer(*hir_crate);