Work on resolving UFCS paths, infinite loop bug in resolve

10 files changed, 169 insertions, 61 deletions

diff --git a/src/ast/ast.cpp b/src/ast/ast.cpp
index b6bc74a2..63c228a6 100644
--- a/src/ast/ast.cpp
+++ b/src/ast/ast.cpp
@@ -106,33 +106,25 @@ SERIALISE_TYPE(ImplDef::, "AST_ImplDef", {
     s.item(m_type);

 })

 

-

-::rust::option<Impl&> Impl::matches(const Path& trait, const TypeRef& type)

+Impl& Impl::get_concrete(const ::std::vector<TypeRef>& param_types)

 {

-    //DEBUG("this = " << *this);

-    ::std::vector<TypeRef>  param_types;

-    

-    if( m_def.matches(param_types, trait, type) == false )

-    {

-        return ::rust::option<Impl&>();

+    if( param_types.size() > 0 )

+    { 

+        for( auto& i : m_concrete_impls )

+        {

+            if( i.first == param_types )

+            {

+                return i.second;

+            }

+        }

+        

+        m_concrete_impls.push_back( make_pair(param_types, this->make_concrete(param_types)) );

+        return m_concrete_impls.back().second;

     }

     else

     {

-        //if( param_types.size() > 0 )

-        //{ 

-        //    for( auto& i : m_concrete_impls )

-        //    {

-        //        if( i.first == param_types )

-        //        {

-        //            return ::rust::option<Impl&>(i.second);

-        //        }

-        //    }

-        //    

-        //    m_concrete_impls.push_back( make_pair(param_types, this->make_concrete(param_types)) );

-        //    return ::rust::option<Impl&>( m_concrete_impls.back().second );

-        //}

+        return *this;

     }

-    return ::rust::option<Impl&>( *this );

 }

 

 Impl Impl::make_concrete(const ::std::vector<TypeRef>& types) const

@@ -239,7 +231,7 @@ bool Crate::is_trait_implicit(const Path& trait) const
  *

  * \return True if the trait is implemented (either exlicitly, or implicitly)

  */

-bool Crate::check_impls_wildcard(const Path& trait, const TypeRef& type)

+bool Crate::check_impls_wildcard(const Path& trait, const TypeRef& type) const

 {

     ::std::vector<TypeRef>  _params;

     TRACE_FUNCTION_F("trait="<<trait<<", type="<<type);

@@ -247,9 +239,9 @@ bool Crate::check_impls_wildcard(const Path& trait, const TypeRef& type)
     // 1. Look for a negative impl for this type

     for( auto implptr : m_neg_impl_index )

     {

-        const ImplDef& impl = *implptr;

+        const ImplDef& neg_impl = *implptr;

         

-        if( impl.matches(_params, trait, type) )

+        if( neg_impl.matches(_params, trait, type) )

         {

             return false;

         }

@@ -271,10 +263,17 @@ bool Crate::check_impls_wildcard(const Path& trait, const TypeRef& type)
     return type.impls_wildcard(*this, trait);

 }

 

-bool Crate::find_impl(const Path& trait, const TypeRef& type, Impl** out_impl)

+bool Crate::find_impl(const Path& trait, const TypeRef& type, Impl** out_impl, ::std::vector<TypeRef>* out_params) const 

 {

     DEBUG("trait = " << trait << ", type = " << type);

     

+    ::std::vector<TypeRef>  dud_params;

+    

+    if(out_params)

+        *out_params = ::std::vector<TypeRef>();

+    else

+        out_params = &dud_params;

+    

     if(out_impl)    *out_impl = nullptr;

     

     if( is_trait_implicit(trait) )

@@ -318,6 +317,7 @@ bool Crate::find_impl(const Path& trait, const TypeRef& type, Impl** out_impl)
         ::std::vector<TypeRef>  _p;

         if( impl.def().matches(_p, trait, TypeRef()) )

         {

+            assert(_p.size() == 0);

             // This is a wildcard trait, need to locate either a negative, or check contents

             if( check_impls_wildcard(trait, type) )

             {

@@ -337,10 +337,9 @@ bool Crate::find_impl(const Path& trait, const TypeRef& type, Impl** out_impl)
     {

         Impl& impl = *implptr;

         // TODO: What if there's two impls that match this combination?

-        ::rust::option<Impl&> oimpl = impl.matches(trait, type);

-        if( oimpl.is_some() )

+        if( impl.def().matches(*out_params, trait, type) )

         {

-            if(out_impl)    *out_impl = &oimpl.unwrap();

+            if(out_impl)    *out_impl = &impl;

             return true;

         }

     }

@@ -935,7 +934,7 @@ bool TypeParams::check_params(Crate& crate, ::std::vector<TypeRef>& types, bool
                 {

                     const auto& trait = bound.bound();

                     // Check if 'type' impls 'trait'

-                    if( !crate.find_impl(trait, trait).is_some() )

+                    if( !crate.find_impl(trait, trait) )

                     {

                         throw ::std::runtime_error( FMT("No matching impl of "<<trait<<" for "<<type));

                     }

diff --git a/src/ast/ast.hpp b/src/ast/ast.hpp
index c3d4860d..f1229fb2 100644
--- a/src/ast/ast.hpp
+++ b/src/ast/ast.hpp
@@ -377,7 +377,7 @@ class Trait:
 {

     MetaItems   m_attrs;

     TypeParams  m_params;

-    ItemList<TypeRef>   m_types;

+    ItemList<TypeAlias> m_types;

     ItemList<Function>  m_functions;

 public:

     Trait() {}

@@ -390,14 +390,14 @@ public:
     const MetaItems& attrs() const { return m_attrs; }

     const TypeParams& params() const { return m_params; }

     const ItemList<Function>& functions() const { return m_functions; }

-    const ItemList<TypeRef>& types() const { return m_types; }

+    const ItemList<TypeAlias>& types() const { return m_types; }

 

     TypeParams& params() { return m_params; }

     ItemList<Function>& functions() { return m_functions; }

-    ItemList<TypeRef>& types() { return m_types; }

+    ItemList<TypeAlias>& types() { return m_types; }

     

     void add_type(::std::string name, TypeRef type) {

-        m_types.push_back( Item<TypeRef>(move(name), move(type), true) );

+        m_types.push_back( Item<TypeAlias>(move(name), TypeAlias(MetaItems(), TypeParams(), move(type)), true) );

     }

     void add_function(::std::string name, Function fcn) {

         m_functions.push_back( Item<Function>(::std::move(name), ::std::move(fcn), true) );

@@ -555,12 +555,15 @@ public:
     ItemList<Function>& functions() { return m_functions; }

     ItemList<TypeRef>& types() { return m_types; }

 

-    Impl make_concrete(const ::std::vector<TypeRef>& types) const;

-

-    ::rust::option<Impl&> matches(const Path& trait, const TypeRef& type);

+    /// Obtain a concrete implementation based on the provided types (caches)

+    Impl& get_concrete(const ::std::vector<TypeRef>& param_types);

     

     friend ::std::ostream& operator<<(::std::ostream& os, const Impl& impl);

     SERIALISABLE_PROTOTYPES();

+    

+private:

+    /// Actually create a concrete impl

+    Impl make_concrete(const ::std::vector<TypeRef>& types) const;

 };

 

 

@@ -785,11 +788,12 @@ public:
     

     bool is_trait_implicit(const Path& trait) const;

     

-    bool find_impl(const Path& trait, const TypeRef& type, Impl** out_impl);

-    ::rust::option<Impl&> find_impl(const Path& trait, const TypeRef& type) {

+    bool find_impl(const Path& trait, const TypeRef& type, Impl** out_impl=nullptr, ::std::vector<TypeRef>* out_prams=nullptr) const;

+    const ::rust::option<Impl&> get_impl(const Path& trait, const TypeRef& type) {

         Impl*   impl_ptr;

-        if( find_impl(trait, type, &impl_ptr) ) {

-            return ::rust::option<Impl&>(*impl_ptr);

+        ::std::vector<TypeRef>  params;

+        if( find_impl(trait, type, &impl_ptr, &params) ) {

+            return ::rust::option<Impl&>( impl_ptr->get_concrete(params) );

         }

         else {

             return ::rust::option<Impl&>();

@@ -803,7 +807,7 @@ public:
 

     SERIALISABLE_PROTOTYPES();

 private:

-    bool check_impls_wildcard(const Path& trait, const TypeRef& type);

+    bool check_impls_wildcard(const Path& trait, const TypeRef& type) const;

 };

 

 /// Representation of an imported crate

diff --git a/src/ast/path.cpp b/src/ast/path.cpp
index 2b1a6fb2..328af8d9 100644
--- a/src/ast/path.cpp
+++ b/src/ast/path.cpp
@@ -310,24 +310,44 @@ ret:
     }
     return ;
 }
+
 void Path::resolve_ufcs(const Crate& root_crate, bool expect_params)
 {
     auto& type = m_ufcs.at(0);
     auto& trait = m_ufcs.at(1);
     
+    // TODO: I can forsee <T>::Assoc::Item desugaring into < <T>::Assoc >::Item, but that will be messy to code
+    assert(m_nodes.size());
+    if(m_nodes.size() != 1) throw ParseError::Todo("Path::resolve_ufcs - Are multi-node UFCS paths valid?");
+    auto& node = m_nodes.at(0);
+    
     // If the type is unknown (at this time)
     if( type.is_wildcard() || type.is_type_param() )
     {
         // - _ as _ = BUG
         if( !trait.is_path() )
         {
+            // Wait, what about <T as _>, is that valid?
             throw CompileError::BugCheck( FMT("Path::resolve_ufcs - Path invalid : " << *this) );
         }
         // - /*arg*/T as Trait = Type parameter
         else if( type.is_type_param() )
         {
-            // Just check that the param is bound on that trait?
-            throw ParseError::Todo("Path::resolve_ufcs - Handle binding on generic");
+            // Check that the param is bound on that trait?
+            if( !type.type_params_ptr() )
+                throw CompileError::BugCheck( FMT("Path::resolve_ufcs - No bound params on arg") );
+            
+            //const auto& tps = *type.type_params_ptr();
+            //for( const auto& bound : tps.bounds() )
+            //{
+            //    // TODO: Check if this type impls the trait
+            //    // - Not needed to do the bind, so ignore for now
+            //}
+            
+            // Search trait for an impl
+            //throw ParseError::Todo("Path::resolve_ufcs - Arg");
+            resolve_ufcs_trait(trait.path(), node);
+            //throw ParseError::Todo("Path::resolve_ufcs - Arg2");
         }
         // - _ as Trait = Inferred type (unknown at the moment)
         else
@@ -340,18 +360,38 @@ void Path::resolve_ufcs(const Crate& root_crate, bool expect_params)
         // - Type as _ = ? Infer the trait from any matching impls
         if( trait.is_wildcard() )
         {
+            // Search inherent impl first, then (somehow) search in-scope traits
+            // - TODO: Shouldn't this be the job of CPathResolver?
             throw ParseError::Todo("Path::resolve_ufcs - Unknown trait (resolve)");
         }
         // - Type as Trait = Obtain from relevant impl
         else if( trait.is_path() )
         {
             // Locate in the trait, but store Self type somehow?
-            throw ParseError::Todo("Path::resolve_ufcs - Fully known");
+            trait.path().resolve(root_crate, true);
+            resolve_ufcs_trait(trait.path(), node);
         }
         // - Type as ! = Item from the inherent impl (similar to above)
         else if( trait == TypeRef(TypeRef::TagInvalid()) )
         {
-            throw ParseError::Todo("Path::resolve_ufcs - Fully known (inherent)");
+            // TODO: Handle case where 'type' is a trait object
+            // 1. Obtain the impl
+            AST::Impl* impl_ptr;
+            if( ! root_crate.find_impl(AST::Path(), type, &impl_ptr) )
+                throw ParseError::Generic("Path::resolve_ufcs - No impl block for type");
+            assert( impl_ptr );
+            
+            for( const auto& it : impl_ptr->functions() )
+            {
+                if( it.name == node.name() ) {
+                    check_param_counts(it.data.params(), expect_params, node);
+                    m_binding = PathBinding(&it.data);
+                    goto _impl_item_bound;
+                }
+            }
+            throw ParseError::Generic("Path::resolve_ufcs - No item in inherent");
+        _impl_item_bound:
+            DEBUG("UFCS inherent bound to " << m_binding);
         }
         // - Type as * = Bug
         else
@@ -360,6 +400,35 @@ void Path::resolve_ufcs(const Crate& root_crate, bool expect_params)
         }
     }
 }
+
+void Path::resolve_ufcs_trait(const AST::Path& trait_path, AST::PathNode& node)
+{
+    if(trait_path.m_binding.type() != PathBinding::TRAIT)
+        throw ParseError::Generic("Path::resolve_ufcs - Trait in UFCS path is not a trait");
+    const auto& trait_def = trait_path.m_binding.bound_trait();
+    
+    // Check that the requested item exists within the trait, and bind to that item
+    for( const auto& fn : trait_def.functions() )
+    {
+        if( fn.name == node.name() ) {
+            check_param_counts(fn.data.params(), true, node);
+            m_binding = PathBinding(&fn.data);
+            goto _trait_item_bound;
+        }
+    }
+    for( const auto& it : trait_def.types() )
+    {
+        if( it.name == node.name() ) {
+            check_param_counts(it.data.params(), true, node);
+            m_binding = PathBinding(&it.data);
+            goto _trait_item_bound;
+        }
+    }
+    throw ParseError::Todo("Path::resolve_ufcs - Fully known");
+_trait_item_bound:
+    DEBUG("UFCS trait bound to " << m_binding);
+}
+
 void Path::check_param_counts(const TypeParams& params, bool expect_params, PathNode& node)
 {
     if( !expect_params )
diff --git a/src/ast/path.hpp b/src/ast/path.hpp
index 8ba9e93c..5028bebc 100644
--- a/src/ast/path.hpp
+++ b/src/ast/path.hpp
@@ -257,6 +257,7 @@ public:
     void resolve(const Crate& crate, bool expect_params=true);
     void resolve_absolute(const Crate& root_crate, bool expect_params);
     void resolve_ufcs(const Crate& root_crate, bool expect_params);
+    void resolve_ufcs_trait(const AST::Path& trait_path, AST::PathNode& node);
     
     /// Resolve generic arguments within the path
     void resolve_args(::std::function<TypeRef(const char*)> fcn);
diff --git a/src/convert/resolve.cpp b/src/convert/resolve.cpp
index 53f20f94..b006a5eb 100644
--- a/src/convert/resolve.cpp
+++ b/src/convert/resolve.cpp
@@ -35,8 +35,12 @@ class CPathResolver:
         {}

         

         friend ::std::ostream& operator<<(::std::ostream& os, const LocalItem& x) {

-            //return os << "'" << x.name << "' = " << x.path;

-            return os << (x.type == TYPE ? "type" : "var") << " '" << x.name << "'";

+            if( x.name == "" )

+                return os << "#";

+            else if( x.type == TYPE )

+                return os << "type '" << x.name << "' = " << x.tr;

+            else

+                return os << "var '" << x.name << "'";

         }

     };

     const AST::Crate&   m_crate;

@@ -62,6 +66,7 @@ public:
 

     virtual void start_scope() override;

     virtual void local_type(::std::string name, TypeRef type) override {

+        DEBUG("(name = " << name << ", type = " << type << ")");

         m_locals.push_back( LocalItem(LocalItem::TYPE, ::std::move(name), ::std::move(type)) );

     }

     virtual void local_variable(bool _is_mut, ::std::string name, const TypeRef& _type) override {

@@ -505,7 +510,26 @@ void CPathResolver::handle_path_int(AST::Path& path, CASTIterator::PathMode mode
         // 1. Handle sub-types

         handle_type(path.ufcs().at(0));

         handle_type(path.ufcs().at(1));

-        // 2. Call resolve to attempt binding

+        // 2. Handle wildcard traits (locate in inherent impl, or from an in-scope trait)

+        if( path.ufcs().at(1).is_wildcard() )

+        {

+            // 1. Inherent

+            AST::Impl*  impl_ptr;

+            ::std::vector<TypeRef> params;

+            if( m_crate.find_impl(AST::Path(), path.ufcs().at(0), &impl_ptr, &params) )

+            {

+                DEBUG("Found matching inherent impl");

+                // - Mark as being from the inherent, and move along

+                //  > TODO: What about if this item is actually from a trait (due to genric restrictions)

+                path.ufcs().at(1) = TypeRef(TypeRef::TagInvalid());

+            }

+            else

+            {            

+                // Iterate all traits in scope, and find one that is impled for this type

+                throw ParseError::Todo("CPathResolver::handle_path - UFCS, find trait");

+            }

+        }

+        // 3. Call resolve to attempt binding

         path.resolve(m_crate);

         break;

     }

@@ -513,6 +537,12 @@ void CPathResolver::handle_path_int(AST::Path& path, CASTIterator::PathMode mode
 void CPathResolver::handle_type(TypeRef& type)

 {

     TRACE_FUNCTION_F("type = " << type);

+    // PROBLEM: Recursion when evaluating Self that expands to UFCS mentioning Self

+    //  > The inner Self shouldn't be touched, but it gets hit by this method, and sudden recursion

+    //if( type.is_locked() )

+    //{

+    //}

+    //else

     if( type.is_path() && type.path().is_trivial() )

     {

         const auto& name = type.path()[0].name();

@@ -551,6 +581,11 @@ void CPathResolver::handle_type(TypeRef& type)
             throw CompileError::Generic( FMT("CPathResolver::handle_type - Invalid parameter '" << name << "'") );

         }

     }

+    else

+    {

+        // No change

+    }

+    DEBUG("type = " << type);

     

     //if( type.is_type_param() && type.type_param() == "Self" )

     //{

diff --git a/src/convert/typecheck_expr.cpp b/src/convert/typecheck_expr.cpp
index 4fb7f174..da64580d 100644
--- a/src/convert/typecheck_expr.cpp
+++ b/src/convert/typecheck_expr.cpp
@@ -503,7 +503,7 @@ void CTC_NodeVisitor::visit(AST::ExprNode_CallMethod& node)
         else
         {
             // 2. Find inherent impl
-            auto oimpl = m_tc.m_crate.find_impl(AST::Path(), ltype);
+            auto oimpl = m_tc.m_crate.get_impl(AST::Path(), ltype);
             if( oimpl.is_some() )
             {
                 AST::Impl& impl = oimpl.unwrap();
@@ -522,7 +522,7 @@ void CTC_NodeVisitor::visit(AST::ExprNode_CallMethod& node)
             // 2. Iterate in-scope traits
             m_tc.iterate_traits( [&](const TypeRef& trait) {
                 // TODO: Check trait first, then find an impl
-                auto oimpl = m_tc.m_crate.find_impl(trait.path(), ltype);
+                auto oimpl = m_tc.m_crate.get_impl(trait.path(), ltype);
                 if( oimpl.is_some() )
                 {
                     AST::Impl& impl = oimpl.unwrap();
diff --git a/src/convert/typecheck_params.cpp b/src/convert/typecheck_params.cpp
index a3a432e0..f3fe5047 100644
--- a/src/convert/typecheck_params.cpp
+++ b/src/convert/typecheck_params.cpp
@@ -126,7 +126,7 @@ bool CGenericParamChecker::has_impl(const TypeRef& type, const AST::Path& trait)
     else
     {
         // Search all known impls of this trait (TODO: keep a list at the crate level) for a match to this type
-        if( m_crate.find_impl(trait, type, NULL) == false ) {
+        if( m_crate.find_impl(trait, type, nullptr, nullptr) == false ) {
             DEBUG("- Nope");
             return false;
         }
diff --git a/src/include/debug.hpp b/src/include/debug.hpp
index 39af8ab0..d11af652 100644
--- a/src/include/debug.hpp
+++ b/src/include/debug.hpp
@@ -6,7 +6,7 @@
 extern int g_debug_indent_level;
 
 #ifndef DISABLE_DEBUG
-#define INDENT()    do { g_debug_indent_level += 1; } while(0)
+#define INDENT()    do { g_debug_indent_level += 1; assert(g_debug_indent_level<100); } while(0)
 #define UNINDENT()    do { g_debug_indent_level -= 1; } while(0)
 #define DEBUG(ss)   do{ if(debug_enabled()) { debug_output(g_debug_indent_level, __FUNCTION__) << ss << ::std::endl; } } while(0)
 #else
diff --git a/src/types.cpp b/src/types.cpp
index 99312d13..25c2f159 100644
--- a/src/types.cpp
+++ b/src/types.cpp
@@ -252,7 +252,7 @@ void TypeRef::match_args(const TypeRef& other, ::std::function<void(const char*,
     }
 }
 
-bool TypeRef::impls_wildcard(AST::Crate& crate, const AST::Path& trait) const
+bool TypeRef::impls_wildcard(const AST::Crate& crate, const AST::Path& trait) const
 {
     switch(m_class)
     {
@@ -274,16 +274,16 @@ bool TypeRef::impls_wildcard(AST::Crate& crate, const AST::Path& trait) const
         return true;
     // Pointers/arrays inherit directly
     case REFERENCE:
-        return crate.find_impl(trait, sub_types()[0], nullptr);
+        return crate.find_impl(trait, sub_types()[0], nullptr, nullptr);
     case POINTER:
-        return crate.find_impl(trait, sub_types()[0], nullptr);
+        return crate.find_impl(trait, sub_types()[0], nullptr, nullptr);
     case ARRAY:
-        return crate.find_impl(trait, sub_types()[0], nullptr);
+        return crate.find_impl(trait, sub_types()[0], nullptr, nullptr);
     // Tuples just destructure
     case TUPLE:
         for( const auto& fld : sub_types() )
         {
-            if( !crate.find_impl(trait, fld, nullptr) )
+            if( !crate.find_impl(trait, fld, nullptr, nullptr) )
                 return false;
         }
         return true;
@@ -308,7 +308,7 @@ bool TypeRef::impls_wildcard(AST::Crate& crate, const AST::Path& trait) const
                 fld_ty.resolve_args( resolve_fn );
                 DEBUG("- Fld '" << fld.name << "' := " << fld.data << " => " << fld_ty);
                 // TODO: Defer failure until after all fields are processed
-                if( !crate.find_impl(trait, fld_ty, nullptr) )
+                if( !crate.find_impl(trait, fld_ty, nullptr, nullptr) )
                     return false;
             }
             return true; }
@@ -323,7 +323,7 @@ bool TypeRef::impls_wildcard(AST::Crate& crate, const AST::Path& trait) const
                     real_ty.resolve_args( resolve_fn );
                     DEBUG("- Var '" << var.m_name << "' := " << ty << " => " << real_ty);
                     // TODO: Defer failure until after all fields are processed
-                    if( !crate.find_impl(trait, real_ty, nullptr) )
+                    if( !crate.find_impl(trait, real_ty, nullptr, nullptr) )
                         return false;
                 }
             }
diff --git a/src/types.hpp b/src/types.hpp
index 5a296e3d..997031de 100644
--- a/src/types.hpp
+++ b/src/types.hpp
@@ -178,7 +178,7 @@ public:
     /// Match 'GENERIC' entries with another type, passing matches to a closure

     void match_args(const TypeRef& other, ::std::function<void(const char*,const TypeRef&)> fcn) const;

     

-    bool impls_wildcard(AST::Crate& crate, const AST::Path& trait) const;

+    bool impls_wildcard(const AST::Crate& crate, const AST::Path& trait) const;

     

     /// Returns true if the type is fully known (all sub-types are not wildcards)

     bool is_concrete() const;