HIR - Build up a flattened list of parent traits early to save time later

15 files changed, 280 insertions, 162 deletions

diff --git a/src/hir/deserialise.cpp b/src/hir/deserialise.cpp
index 40fd1aca..1dbcc576 100644
--- a/src/hir/deserialise.cpp
+++ b/src/hir/deserialise.cpp
@@ -894,13 +894,14 @@ namespace {
         ::HIR::Trait rv {
             deserialise_genericparams(),
             "",  // TODO: Better type for lifetime
-            deserialise_vec< ::HIR::TraitPath>()
+            {}
             };
         rv.m_is_marker = m_in.read_bool();
         rv.m_types = deserialise_strumap< ::HIR::AssociatedType>();
         rv.m_values = deserialise_strumap< ::HIR::TraitValueItem>();
         rv.m_value_indexes = deserialise_strummap< ::std::pair<unsigned int, ::HIR::GenericPath> >();
         rv.m_type_indexes = deserialise_strumap< unsigned int>();
+        rv.m_all_parent_traits = deserialise_vec< ::HIR::TraitPath>();
         return rv;
     }
 
diff --git a/src/hir/from_ast.cpp b/src/hir/from_ast.cpp
index 8ad46596..b9a98f58 100644
--- a/src/hir/from_ast.cpp
+++ b/src/hir/from_ast.cpp
@@ -945,6 +945,7 @@ namespace {
             this_trait.m_params.m_types.push_back( ::HIR::TypeRef(arg.m_name, i) );
             i ++;
         }
+        // HACK: Add a bound of Self: ThisTrait for parts of typeck (TODO: Remove this, it's evil)
         rv.m_params.m_bounds.push_back( ::HIR::GenericBound::make_TraitBound({ ::HIR::TypeRef("Self",0xFFFF), { mv$(this_trait) } }) );
     }
 
diff --git a/src/hir/hir.cpp b/src/hir/hir.cpp
index 780a8e70..66dc0e0b 100644
--- a/src/hir/hir.cpp
+++ b/src/hir/hir.cpp
@@ -460,13 +460,11 @@ namespace {
         const auto& tr = *cur_trait.m_trait_ptr;
         auto monomorph_cb = monomorphise_type_get_cb(sp, &type, &cur_trait.m_path.m_params, nullptr);
 
-        for(const auto& trait_path_raw : tr.m_parent_traits)
+        for(const auto& trait_path_raw : tr.m_all_parent_traits)
         {
             // 1. Monomorph
             auto trait_path_mono = monomorphise_traitpath_with(sp, trait_path_raw, monomorph_cb, false);
-            // 2. Recurse
-            add_bound_from_trait(rv, type, trait_path_mono);
-            // 3. Add
+            // 2. Add
             rv.push_back( ::HIR::GenericBound::make_TraitBound({ type.clone(), mv$(trait_path_mono) }) );
         }
 
diff --git a/src/hir/hir.hpp b/src/hir/hir.hpp
index f090c67f..c72fff4b 100644
--- a/src/hir/hir.hpp
+++ b/src/hir/hir.hpp
@@ -285,6 +285,9 @@ struct Trait
     // Indexes in the vtable parameter list for each associated type
     ::std::unordered_map< ::std::string, unsigned int > m_type_indexes;
 
+    // Flattend set of parent traits (monomorphised and associated types fixed)
+    ::std::vector< ::HIR::TraitPath >  m_all_parent_traits;
+
     Trait( GenericParams gps, ::std::string lifetime, ::std::vector< ::HIR::TraitPath> parents):
         m_params( mv$(gps) ),
         m_lifetime( mv$(lifetime) ),
diff --git a/src/hir/path.hpp b/src/hir/path.hpp
index 80fb4caa..eb9aca27 100644
--- a/src/hir/path.hpp
+++ b/src/hir/path.hpp
@@ -162,6 +162,7 @@ public:
 
     bool operator==(const TraitPath& x) const;
     bool operator!=(const TraitPath& x) const { return !(*this == x); }
+    bool operator<(const TraitPath& x) const { return ord(x) == OrdLess; }
 
     Ordering ord(const TraitPath& x) const {
         ORD(m_path, x.m_path);
diff --git a/src/hir/serialise.cpp b/src/hir/serialise.cpp
index 59b43a4e..87cf5723 100644
--- a/src/hir/serialise.cpp
+++ b/src/hir/serialise.cpp
@@ -874,12 +874,12 @@ namespace {
             TRACE_FUNCTION_F("_trait:");
             serialise_generics(item.m_params);
             //m_out.write_string(item.m_lifetime);    // TODO: Better type for lifetime
-            serialise_vec( item.m_parent_traits );
             m_out.write_bool( item.m_is_marker );
             serialise_strmap( item.m_types );
             serialise_strmap( item.m_values );
             serialise_strmap( item.m_value_indexes );
             serialise_strmap( item.m_type_indexes );
+            serialise_vec( item.m_all_parent_traits );
         }
         void serialise(const ::HIR::TraitValueItem& tvi)
         {
diff --git a/src/hir/visitor.cpp b/src/hir/visitor.cpp
index 02cc5948..77bc1a1b 100644
--- a/src/hir/visitor.cpp
+++ b/src/hir/visitor.cpp
@@ -164,6 +164,9 @@ void ::HIR::Visitor::visit_trait(::HIR::ItemPath p, ::HIR::Trait& item)
     for(auto& par : item.m_parent_traits) {
         this->visit_trait_path(par);
     }
+    for(auto& par : item.m_all_parent_traits) {
+        this->visit_trait_path(par);
+    }
     for(auto& i : item.m_types) {
         DEBUG("type " << i.first);
         for(auto& bound : i.second.m_trait_bounds)
diff --git a/src/hir_conv/markings.cpp b/src/hir_conv/markings.cpp
index e40ce537..d867fc06 100644
--- a/src/hir_conv/markings.cpp
+++ b/src/hir_conv/markings.cpp
@@ -3,7 +3,7 @@
  * - By John Hodge (Mutabah/thePowersGang)
  *
  * hir_conv/markings.cpp
- * - Fills the TraitMarkings structure on types
+ * - Fills the TraitMarkings structure on types as well as other metadata
  */
 #include "main_bindings.hpp"
 #include <hir/visitor.hpp>
@@ -45,6 +45,161 @@ public:
         }
     }
 
+    void visit_trait(::HIR::ItemPath ip, ::HIR::Trait& tr) override
+    {
+        static Span sp;
+        TRACE_FUNCTION_F(ip);
+
+        // Enumerate supertraits and save for later stages
+        struct Enumerate
+        {
+            ::std::vector< ::HIR::TraitPath>    supertraits;
+
+            void enum_supertraits_in(const ::HIR::Trait& tr, ::HIR::GenericPath path, ::std::function<::HIR::TypeRef(const char*)> get_aty)
+            {
+                TRACE_FUNCTION_F(path);
+
+                // Fill defaulted parameters.
+                // NOTE: Doesn't do much error checking.
+                if( path.m_params.m_types.size() != tr.m_params.m_types.size() )
+                {
+                    ASSERT_BUG(sp, path.m_params.m_types.size() < tr.m_params.m_types.size(), "");
+                    for(unsigned int i = path.m_params.m_types.size(); i < tr.m_params.m_types.size(); i ++)
+                    {
+                        const auto& def = tr.m_params.m_types[i];
+                        path.m_params.m_types.push_back( def.m_default.clone() );
+                    }
+                }
+
+                ::HIR::TypeRef  ty_self { "Self", 0xFFFF };
+                auto monomorph_cb = monomorphise_type_get_cb(sp, &ty_self, &path.m_params, nullptr);
+                // Recurse into parent traits
+                for(const auto& pt : tr.m_parent_traits)
+                {
+                    auto get_aty_this = [&](const char* name) {
+                        auto it = pt.m_type_bounds.find(name);
+                        if( it != pt.m_type_bounds.end() )
+                            return monomorphise_type_with(sp, it->second, monomorph_cb);
+                        return get_aty(name);
+                        };
+                    enum_supertraits_in(*pt.m_trait_ptr, monomorphise_genericpath_with(sp, pt.m_path, monomorph_cb, false), get_aty_this);
+                }
+                // - Bound parent traits
+                for(const auto& b : tr.m_params.m_bounds)
+                {
+                    if( !b.is_TraitBound() )
+                        continue;
+                    const auto& be = b.as_TraitBound();
+                    if( be.type != ::HIR::TypeRef("Self", 0xFFFF) )
+                        continue;
+                    const auto& pt = be.trait;
+                    if( pt.m_path.m_path == path.m_path )
+                        continue ;
+
+                    auto get_aty_this = [&](const char* name) {
+                        auto it = pt.m_type_bounds.find(name);
+                        if( it != pt.m_type_bounds.end() )
+                            return monomorphise_type_with(sp, it->second, monomorph_cb);
+                        return get_aty(name);
+                        };
+
+                    enum_supertraits_in(*pt.m_trait_ptr, monomorphise_genericpath_with(sp, pt.m_path, monomorph_cb, false), get_aty_this);
+                }
+
+
+                // Build output path.
+                ::HIR::TraitPath    out_path;
+                out_path.m_path = mv$(path);
+                out_path.m_trait_ptr = &tr;
+                // - Locate associated types for this trait
+                for(const auto& ty : tr.m_types)
+                {
+                    auto v = get_aty(ty.first.c_str());
+                    if( v != ::HIR::TypeRef() )
+                    {
+                        out_path.m_type_bounds.insert( ::std::make_pair(ty.first, mv$(v)) );
+                    }
+                }
+                // TODO: HRLs?
+                supertraits.push_back( mv$(out_path) );
+            }
+        };
+
+        auto this_path = ip.get_simple_path();
+        this_path.m_crate_name = m_crate.m_crate_name;
+
+        Enumerate   e;
+        for(const auto& pt : tr.m_parent_traits)
+        {
+            auto get_aty = [&](const char* name) {
+                auto it = pt.m_type_bounds.find(name);
+                if( it != pt.m_type_bounds.end() )
+                    return it->second.clone();
+                return ::HIR::TypeRef();
+                };
+            e.enum_supertraits_in(*pt.m_trait_ptr, pt.m_path.clone(), get_aty);
+        }
+        for(const auto& b : tr.m_params.m_bounds)
+        {
+            if( !b.is_TraitBound() )
+                continue;
+            const auto& be = b.as_TraitBound();
+            if( be.type != ::HIR::TypeRef("Self", 0xFFFF) )
+                continue;
+            const auto& pt = be.trait;
+
+            // TODO: Remove this along with the from_ast.cpp hack
+            if( pt.m_path.m_path == this_path )
+            {
+                // TODO: Should this restrict based on the parameters
+                continue ;
+            }
+
+            auto get_aty = [&](const char* name) {
+                auto it = be.trait.m_type_bounds.find(name);
+                if( it != be.trait.m_type_bounds.end() )
+                    return it->second.clone();
+                return ::HIR::TypeRef();
+                };
+            e.enum_supertraits_in(*be.trait.m_trait_ptr, be.trait.m_path.clone(), get_aty);
+        }
+
+        ::std::sort(e.supertraits.begin(), e.supertraits.end());
+        DEBUG("supertraits = " << e.supertraits);
+        if( e.supertraits.size() > 0 )
+        {
+            bool dedeup_done = false;
+            auto prev = e.supertraits.begin();
+            for(auto it = e.supertraits.begin()+1; it != e.supertraits.end(); )
+            {
+                if( prev->m_path == it->m_path )
+                {
+                    if( *prev == *it ) {
+                    }
+                    else if( prev->m_type_bounds.size() == 0 ) {
+                        ::std::swap(*prev, *it);
+                    }
+                    else if( it->m_type_bounds.size() == 0 ) {
+                    }
+                    else {
+                        TODO(sp, "Merge associated types from " << *prev << " and " << *it);
+                    }
+                    it = e.supertraits.erase(it);
+                    dedeup_done = true;
+                }
+                else
+                {
+                    ++ it;
+                    ++ prev;
+                }
+            }
+            if( dedeup_done ) {
+                DEBUG("supertraits dd = " << e.supertraits);
+            }
+        }
+        tr.m_all_parent_traits = mv$(e.supertraits);
+    }
+
     ::HIR::TraitMarkings::DstType get_field_dst_type(const ::HIR::TypeRef& ty, const ::HIR::GenericParams& inner_def, const ::HIR::GenericParams& params_def, const ::HIR::PathParams* params)
     {
         // If the type is generic, and the pointed-to parameters is ?Sized, record as needing unsize
diff --git a/src/hir_conv/resolve_ufcs.cpp b/src/hir_conv/resolve_ufcs.cpp
index 03cbd168..9f3541bd 100644
--- a/src/hir_conv/resolve_ufcs.cpp
+++ b/src/hir_conv/resolve_ufcs.cpp
@@ -359,6 +359,7 @@ namespace {
 
 
             // Search supertraits (recursively)
+            // NOTE: This runs before "Resolve HIR Markings", so m_all_parent_traits can't be used.
             for( unsigned int i = 0; i < trait.m_parent_traits.size(); i ++ )
             {
                 const auto& par_trait_path = trait.m_parent_traits[i].m_path;
diff --git a/src/hir_expand/vtable.cpp b/src/hir_expand/vtable.cpp
index f366a7d4..12a5f416 100644
--- a/src/hir_expand/vtable.cpp
+++ b/src/hir_expand/vtable.cpp
@@ -75,10 +75,6 @@ namespace {
                         }
                         i ++;
                     }
-                    for(const auto& st : tr.m_parent_traits) {
-                        add_types_from_trait(*st.m_trait_ptr);
-                    }
-                    // TODO: Iterate supertraits from bounds too
                 }
             };
             Foo visitor { &tr, {}, static_cast<unsigned int>(tr.m_params.m_types.size()) };
@@ -86,6 +82,8 @@ namespace {
                 visitor.params.m_types.push_back( ::HIR::TypeParamDef { tp.m_name, {}, tp.m_is_sized } );
             }
             visitor.add_types_from_trait(tr);
+            for(const auto& st : tr.m_all_parent_traits)
+                visitor.add_types_from_trait(*st.m_trait_ptr);
             auto args = mv$(visitor.params);
 
             struct VtableConstruct {
@@ -149,9 +147,10 @@ namespace {
                             ::HIR::TypeRef  fcn_type( mv$(ft) );
 
                             // Detect use of `Self` and don't create the vtable if there is.
+                            // NOTE: Associated types where replaced by clone_ty_with
                             if( visit_ty_with(fcn_type, [&](const auto& t){ return (t == ::HIR::TypeRef("Self", 0xFFFF)); }) )
                             {
-                                DEBUG("- '" << vi.first << "' NOT object safe (Self), not creating vtable - " << fcn_type);
+                                DEBUG("- '" << vi.first << "' NOT object safe (uses Self), not creating vtable - " << fcn_type);
                                 return false;
                             }
 
@@ -176,13 +175,12 @@ namespace {
                             )
                         )
                     }
-                    for(const auto& st : tr.m_parent_traits) {
+                    for(const auto& st : tr.m_all_parent_traits) {
                         ::HIR::TypeRef  self("Self", 0xFFFF);
                         auto st_gp = monomorphise_genericpath_with(sp, st.m_path, monomorphise_type_get_cb(sp, &self, &trait_path.m_params, nullptr), false);
                         // NOTE: Doesn't trigger non-object-safe
                         add_ents_from_trait(*st.m_trait_ptr, st_gp);
                     }
-                    // TODO: Iterate supertraits from bounds too
                     return true;
                 }
             };
diff --git a/src/hir_typeck/expr_check.cpp b/src/hir_typeck/expr_check.cpp
index f435696e..4f7bb5f4 100644
--- a/src/hir_typeck/expr_check.cpp
+++ b/src/hir_typeck/expr_check.cpp
@@ -767,7 +767,8 @@ namespace {
                     // TODO: Either - Don't include the above impl bound, or change the below trait to the one that has that type
                     for( const auto& assoc : be.trait.m_type_bounds ) {
                         ::HIR::GenericPath  type_trait_path;
-                        m_resolve.trait_contains_type(sp, real_trait, *be.trait.m_trait_ptr, assoc.first,  type_trait_path);
+                        bool has_ty = m_resolve.trait_contains_type(sp, real_trait, *be.trait.m_trait_ptr, assoc.first,  type_trait_path);
+                        ASSERT_BUG(sp, has_ty, "Type " << assoc.first << " not found in chain of " << real_trait);
 
                         auto other_ty = monomorphise_type_with(sp, assoc.second, cache.m_monomorph_cb, true);
 
diff --git a/src/hir_typeck/expr_cs.cpp b/src/hir_typeck/expr_cs.cpp
index cd6f21ae..57bad017 100644
--- a/src/hir_typeck/expr_cs.cpp
+++ b/src/hir_typeck/expr_cs.cpp
@@ -245,7 +245,8 @@ namespace {
                     ::HIR::GenericPath  type_trait_path;
                     ASSERT_BUG(sp, be.trait.m_trait_ptr, "Trait pointer not set in " << be.trait.m_path);
                     // TODO: Store the source trait for this bound in the the bound list?
-                    context.m_resolve.trait_contains_type(sp, real_trait, *be.trait.m_trait_ptr, assoc.first,  type_trait_path);
+                    if( !context.m_resolve.trait_contains_type(sp, real_trait, *be.trait.m_trait_ptr, assoc.first,  type_trait_path) )
+                        BUG(sp, "Couldn't find associated type " << assoc.first << " in trait " << real_trait);
 
                     auto other_ty = monomorphise_type_with(sp, assoc.second, monomorph_cb, true);
 
diff --git a/src/hir_typeck/helpers.cpp b/src/hir_typeck/helpers.cpp
index de4be11d..f7aaa2a5 100644
--- a/src/hir_typeck/helpers.cpp
+++ b/src/hir_typeck/helpers.cpp
@@ -2219,7 +2219,7 @@ bool TraitResolution::find_named_trait_in_trait(const Span& sp,
         }
         };
 
-    for( const auto& pt : trait_ptr.m_parent_traits )
+    for( const auto& pt : trait_ptr.m_all_parent_traits )
     {
         auto pt_mono = monomorphise_traitpath_with(sp, pt, monomorph_cb, false);
 
@@ -2233,42 +2233,6 @@ bool TraitResolution::find_named_trait_in_trait(const Span& sp,
             //}
             return true;
         }
-
-        const auto& tr = m_crate.get_trait_by_path(sp, pt.m_path.m_path);
-        if( find_named_trait_in_trait(sp, des, des_params,  tr, pt.m_path.m_path, pt_mono.m_path.m_params,  target_type, callback) ) {
-            return true;
-        }
-    }
-
-    // Also check bounds for `Self: T` bounds
-    for(const auto& b : trait_ptr.m_params.m_bounds)
-    {
-        if( !b.is_TraitBound() )    continue;
-        const auto& be = b.as_TraitBound();
-
-        if( be.type == ::HIR::TypeRef("Self", 0xFFFF) )
-        {
-            // Something earlier adds a "Self: SelfTrait" bound, prevent that from causing infinite recursion
-            if( be.trait.m_path.m_path == trait_path )
-                continue ;
-            auto pt_mono = monomorphise_traitpath_with(sp, be.trait, monomorph_cb, false);
-            DEBUG(be.trait << " (Bound) => " << pt_mono);
-
-            if( pt_mono.m_path.m_path == des ) {
-                // NOTE: Doesn't quite work...
-                //auto cmp = this->compare_pp(sp, pt_mono.m_path.m_params, des_params);
-                //if( cmp != ::HIR::Compare::Unequal )
-                //{
-                    callback( target_type, pt_mono.m_path.m_params, pt_mono.m_type_bounds );
-                //}
-                return true;
-            }
-
-            const auto& tr = m_crate.get_trait_by_path(sp, pt_mono.m_path.m_path);
-            if( find_named_trait_in_trait(sp, des, des_params,  tr, pt_mono.m_path.m_path, pt_mono.m_path.m_params,  target_type, callback) ) {
-                return true;
-            }
-        }
     }
 
     return false;
@@ -2962,49 +2926,64 @@ bool TraitResolution::find_trait_impls_crate(const Span& sp,
     return match;
 }
 
-bool TraitResolution::trait_contains_method(const Span& sp, const ::HIR::GenericPath& trait_path, const ::HIR::Trait& trait_ptr, const ::HIR::TypeRef& self, const ::std::string& name, AllowedReceivers ar,  ::HIR::GenericPath& out_path) const
-{
-    auto it = trait_ptr.m_values.find(name);
-    if( it != trait_ptr.m_values.end() ) {
-        if( it->second.is_Function() ) {
-            const auto& v = it->second.as_Function();
-            switch(v.m_receiver)
-            {
-            case ::HIR::Function::Receiver::Free:
-                break;
-            case ::HIR::Function::Receiver::Value:
-                if( ar != AllowedReceivers::All && ar != AllowedReceivers::Value )
-                    break;
-                if(0)
-            case ::HIR::Function::Receiver::Box:
-                if( ar != AllowedReceivers::Box )
+namespace {
+    bool trait_contains_method_(const ::HIR::Trait& trait_ptr, const ::std::string& name, TraitResolution::AllowedReceivers ar)
+    {
+        auto it = trait_ptr.m_values.find(name);
+        if( it != trait_ptr.m_values.end() )
+        {
+            if( it->second.is_Function() ) {
+                const auto& v = it->second.as_Function();
+                switch(v.m_receiver)
+                {
+                case ::HIR::Function::Receiver::Free:
                     break;
-            default:
-                out_path = trait_path.clone();
-                return true;
+                case ::HIR::Function::Receiver::Value:
+                    if( ar != TraitResolution::AllowedReceivers::All && ar != TraitResolution::AllowedReceivers::Value )
+                        break;
+                    if(0)
+                case ::HIR::Function::Receiver::Box:
+                    if( ar != TraitResolution::AllowedReceivers::Box )
+                        break;
+                default:
+                    return true;
+                }
             }
         }
+        return false;
     }
+}
+
+bool TraitResolution::trait_contains_method(const Span& sp, const ::HIR::GenericPath& trait_path, const ::HIR::Trait& trait_ptr, const ::HIR::TypeRef& self, const ::std::string& name, AllowedReceivers ar,  ::HIR::GenericPath& out_path) const
+{
+    TRACE_FUNCTION_FR(trait_path << " has " << name, out_path);
 
-    // TODO: Prevent infinite recursion
-    for(const auto& st : trait_ptr.m_parent_traits)
+    if( trait_contains_method_(trait_ptr, name, ar) )
     {
-        auto& st_ptr = this->m_crate.get_trait_by_path(sp, st.m_path.m_path);
-        if( trait_contains_method(sp, st.m_path, st_ptr, self, name, ar,  out_path) ) {
-            out_path.m_params = monomorphise_path_params_with(sp, mv$(out_path.m_params), [&](const auto& gt)->const auto& {
-                const auto& ge = gt.m_data.as_Generic();
-                if( ge.binding == 0xFFFF ) {
-                    return self;
-                }
-                else if( (ge.binding >> 8) == 0 ) {
-                    auto idx = ge.binding & 0xFF;
-                    assert(idx < trait_path.m_params.m_types.size());
-                }
-                else {
-                    BUG(sp, "Unexpected type parameter " << gt);
-                }
+        out_path = trait_path.clone();
+        return true;
+    }
+
+    auto monomorph_cb = [&](const auto& gt)->const auto& {
+            const auto& ge = gt.m_data.as_Generic();
+            if( ge.binding == 0xFFFF ) {
+                return self;
+            }
+            else if( (ge.binding >> 8) == 0 ) {
+                auto idx = ge.binding & 0xFF;
+                assert(idx < trait_path.m_params.m_types.size());
                 return trait_path.m_params.m_types[ge.binding];
-                }, false);
+            }
+            else {
+                BUG(sp, "Unexpected type parameter " << gt);
+            }
+            };
+    for(const auto& st : trait_ptr.m_all_parent_traits)
+    {
+        if( trait_contains_method_(*st.m_trait_ptr, name, ar) )
+        {
+            out_path.m_path = st.m_path.m_path;
+            out_path.m_params = monomorphise_path_params_with(sp, st.m_path.m_params, monomorph_cb, false);
             return true;
         }
     }
@@ -3012,24 +2991,28 @@ bool TraitResolution::trait_contains_method(const Span& sp, const ::HIR::Generic
 }
 bool TraitResolution::trait_contains_type(const Span& sp, const ::HIR::GenericPath& trait_path, const ::HIR::Trait& trait_ptr, const ::std::string& name,  ::HIR::GenericPath& out_path) const
 {
+    TRACE_FUNCTION_FR(trait_path << " has " << name, out_path);
+
     auto it = trait_ptr.m_types.find(name);
     if( it != trait_ptr.m_types.end() ) {
+        DEBUG("- Found in cur");
         out_path = trait_path.clone();
         return true;
     }
 
-    auto monomorph = [&](const auto& gt)->const auto& {
+    auto monomorph_cb = [&](const auto& gt)->const auto& {
             const auto& ge = gt.m_data.as_Generic();
             assert(ge.binding < 256);
             assert(ge.binding < trait_path.m_params.m_types.size());
             return trait_path.m_params.m_types[ge.binding];
             };
-    // TODO: Prevent infinite recursion
-    for(const auto& st : trait_ptr.m_parent_traits)
+    for(const auto& st : trait_ptr.m_all_parent_traits)
     {
-        auto& st_ptr = this->m_crate.get_trait_by_path(sp, st.m_path.m_path);
-        if( trait_contains_type(sp, st.m_path, st_ptr, name, out_path) ) {
-            out_path.m_params = monomorphise_path_params_with(sp, mv$(out_path.m_params), monomorph, false);
+        if( st.m_trait_ptr->m_types.count(name) )
+        {
+            DEBUG("- Found in " << st);
+            out_path.m_path = st.m_path.m_path;
+            out_path.m_params = monomorphise_path_params_with(sp, st.m_path.m_params, monomorph_cb, false);
             return true;
         }
     }
diff --git a/src/hir_typeck/outer.cpp b/src/hir_typeck/outer.cpp
index 5f5e5a75..c3f4e770 100644
--- a/src/hir_typeck/outer.cpp
+++ b/src/hir_typeck/outer.cpp
@@ -356,36 +356,36 @@ namespace {
                 pd = get_ufcs_known(mv$(pd.as_UfcsUnknown()), make_generic_path(trait_path.m_path, trait), trait);
                 return true;
             }
-            // Search supertraits (recursively)
-            for( unsigned int i = 0; i < trait.m_parent_traits.size(); i ++ )
+            // Search all supertraits
+            for( const auto& pt : trait.m_all_parent_traits )
             {
-                const auto& par_trait_path = trait.m_parent_traits[i].m_path;
-                //const auto& par_trait_ent = *trait.m_parent_trait_ptrs[i];
-                const auto& par_trait_ent = this->crate.get_trait_by_path(sp, par_trait_path.m_path);
-                if( locate_in_trait_and_set(sp, pc, par_trait_path, par_trait_ent,  pd) ) {
+                if( locate_item_in_trait(pc, *pt.m_trait_ptr, pd) )
+                {
+                    pd = get_ufcs_known(mv$(pd.as_UfcsUnknown()), make_generic_path(trait_path.m_path, trait), trait);
                     return true;
                 }
             }
             return false;
         }
+        bool set_from_impl(const ::HIR::GenericPath& trait_path, const ::HIR::Trait& trait,  ::HIR::Path::Data& pd)
+        {
+            auto& e = pd.as_UfcsUnknown();
+            const auto& type = *e.type;
+            return this->crate.find_trait_impls(trait_path.m_path, type, [](const auto& x)->const auto&{return x;}, [&](const auto& impl) {
+                DEBUG("FOUND impl" << impl.m_params.fmt_args() << " " << trait_path.m_path << impl.m_trait_args << " for " << impl.m_type);
+                // TODO: Check bounds
+                for(const auto& bound : impl.m_params.m_bounds) {
+                    DEBUG("- TODO: Bound " << bound);
+                    return false;
+                }
+                pd = get_ufcs_known(mv$(e), make_generic_path(trait_path.m_path, trait), trait);
+                return true;
+                });
+        }
         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;
-
             auto& e = pd.as_UfcsUnknown();
-            //if( this->m_resolve.trait_contains_type(sp, trait_path, trait, e.item,  out_path) )
             if( this->locate_item_in_trait(pc, trait,  pd) ) {
-                const auto& type = *e.type;
-
-                return this->crate.find_trait_impls(trait_path.m_path, type, [](const auto& x)->const auto&{return x;}, [&](const auto& impl) {
-                    DEBUG("FOUND impl" << impl.m_params.fmt_args() << " " << trait_path.m_path << impl.m_trait_args << " for " << impl.m_type);
-                    // TODO: Check bounds
-                    for(const auto& bound : impl.m_params.m_bounds) {
-                        DEBUG("- TODO: Bound " << bound);
-                        return false;
-                    }
-                    pd = get_ufcs_known(mv$(e), make_generic_path(trait_path.m_path, trait), trait);
-                    return true;
-                    });
+                return this->set_from_impl(trait_path, trait, pd);
             }
             else {
                 DEBUG("- Item " << e.item << " not in trait " << trait_path.m_path);
@@ -393,14 +393,15 @@ namespace {
 
 
             // Search supertraits (recursively)
-            for( unsigned int i = 0; i < trait.m_parent_traits.size(); i ++ )
+            for( const auto& pt : trait.m_all_parent_traits )
             {
-                const auto& par_trait_path = trait.m_parent_traits[i].m_path;
-                //const auto& par_trait_ent = *trait.m_parent_trait_ptrs[i];
-                const auto& par_trait_ent = this->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) ) {
-                    return true;
+                if( this->locate_item_in_trait(pc, *pt.m_trait_ptr, pd) )
+                {
+                    // TODO: Monomorphise params?
+                    return set_from_impl(pt.m_path, *pt.m_trait_ptr, pd);
+                }
+                else
+                {
                 }
             }
             return false;
diff --git a/src/hir_typeck/static.cpp b/src/hir_typeck/static.cpp
index 32fb817e..c99e606f 100644
--- a/src/hir_typeck/static.cpp
+++ b/src/hir_typeck/static.cpp
@@ -455,7 +455,7 @@ bool StaticTraitResolve::find_impl__check_crate_raw(
     ) const
 {
     auto cb_ident = [](const auto&ty)->const auto&{return ty;};
-    DEBUG("impl" << impl_params_def.fmt_args() << " " << des_trait_path << impl_trait_params << " for " << impl_type << impl_params_def.fmt_bounds());
+    TRACE_FUNCTION_F("impl" << impl_params_def.fmt_args() << " " << des_trait_path << impl_trait_params << " for " << impl_type << impl_params_def.fmt_bounds());
 
     ::std::vector< const ::HIR::TypeRef*> impl_params;
     impl_params.resize( impl_params_def.m_types.size() );
@@ -1154,52 +1154,23 @@ bool StaticTraitResolve::find_named_trait_in_trait(const Span& sp,
         }
         };
 
-    for( const auto& pt : trait_ptr.m_parent_traits )
+    for( const auto& pt : trait_ptr.m_all_parent_traits )
     {
         auto pt_mono = monomorphise_traitpath_with(sp, pt, monomorph_cb, false);
 
         DEBUG(pt << " => " << pt_mono);
-        if( pt.m_path.m_path == des && pt_mono.m_path.m_params == des_params ) {
+        if( pt.m_path.m_path == des && pt_mono.m_path.m_params == des_params )
+        {
             callback( pt_mono.m_path.m_params, mv$(pt_mono.m_type_bounds) );
             return true;
         }
-
-        const auto& tr = m_crate.get_trait_by_path(sp, pt.m_path.m_path);
-        if( find_named_trait_in_trait(sp, des, des_params,  tr, pt.m_path.m_path, pt_mono.m_path.m_params,  target_type, callback) ) {
-            return true;
-        }
-    }
-
-    // Also check bounds for `Self: T` bounds
-    for(const auto& b : trait_ptr.m_params.m_bounds)
-    {
-        if( !b.is_TraitBound() )    continue;
-        const auto& be = b.as_TraitBound();
-
-        if( be.type == ::HIR::TypeRef("Self", 0xFFFF) )
-        {
-            // Something earlier adds a "Self: SelfTrait" bound, prevent that from causing infinite recursion
-            if( be.trait.m_path.m_path == trait_path )
-                continue ;
-            auto pt_mono = monomorphise_traitpath_with(sp, be.trait, monomorph_cb, false);
-            DEBUG(be.trait << " (Bound) => " << pt_mono);
-
-            if( pt_mono.m_path.m_path == des ) {
-                callback( pt_mono.m_path.m_params, mv$(pt_mono.m_type_bounds) );
-                return true;
-            }
-
-            const auto& tr = m_crate.get_trait_by_path(sp, pt_mono.m_path.m_path);
-            if( find_named_trait_in_trait(sp, des, des_params,  tr, pt_mono.m_path.m_path, pt_mono.m_path.m_params,  target_type, callback) ) {
-                return true;
-            }
-        }
     }
 
     return false;
 }
 bool StaticTraitResolve::trait_contains_type(const Span& sp, const ::HIR::GenericPath& trait_path, const ::HIR::Trait& trait_ptr, const ::std::string& name,  ::HIR::GenericPath& out_path) const
 {
+    TRACE_FUNCTION_FR("name="<<name << ", trait=" << trait_path, out_path);
     auto it = trait_ptr.m_types.find(name);
     if( it != trait_ptr.m_types.end() ) {
         out_path = trait_path.clone();
@@ -1212,12 +1183,12 @@ bool StaticTraitResolve::trait_contains_type(const Span& sp, const ::HIR::Generi
             assert(ge.binding < trait_path.m_params.m_types.size());
             return trait_path.m_params.m_types[ge.binding];
             };
-    // TODO: Prevent infinite recursion
-    for(const auto& st : trait_ptr.m_parent_traits)
+    for(const auto& st : trait_ptr.m_all_parent_traits)
     {
-        auto& st_ptr = this->m_crate.get_trait_by_path(sp, st.m_path.m_path);
-        if( trait_contains_type(sp, st.m_path, st_ptr, name, out_path) ) {
-            out_path.m_params = monomorphise_path_params_with(sp, mv$(out_path.m_params), monomorph, false);
+        if( st.m_trait_ptr->m_types.count(name) )
+        {
+            out_path.m_path = st.m_path.m_path;
+            out_path.m_params = monomorphise_path_params_with(sp, st.m_path.m_params, monomorph, false);
             return true;
         }
     }