HIR TypeCheck - Initial work on a module-level pass (no inferrence)

12 files changed, 250 insertions, 28 deletions

diff --git a/Makefile b/Makefile
index e43578d5..8e3d6cda 100644
--- a/Makefile
+++ b/Makefile
@@ -47,6 +47,7 @@ OBJ +=  hir/crate_ptr.o hir/type_ptr.o hir/expr_ptr.o
 OBJ +=  hir/type.o hir/path.o hir/expr.o
 OBJ +=  hir/visitor.o
 OBJ += hir_conv/expand_type.o hir_conv/constant_evaluation.o hir_conv/resolve_ufcs.o
+OBJ += hir_typeck/outer.o
 OBJ += dump_as_rust.o
 
 PCHS := ast/ast.hpp
diff --git a/src/hir/from_ast.cpp b/src/hir/from_ast.cpp
index 011fb6c4..26d7029f 100644
--- a/src/hir/from_ast.cpp
+++ b/src/hir/from_ast.cpp
@@ -345,7 +345,10 @@
         for(const auto& param : e.nodes.back().args()) {
             params.m_types.push_back( LowerHIR_Type(param) );
         }
-        return ::HIR::GenericPath(mv$(sp), mv$(params));
+        // TODO: Lifetime params (not encoded in AST::PathNode as yet)
+        auto rv = ::HIR::GenericPath(mv$(sp), mv$(params));
+        DEBUG(path << " => " << rv);
+        return rv;
     )
     else {
         BUG(sp, "Encountered non-Absolute path when creating ::HIR::GenericPath - " << path);
diff --git a/src/hir/type.hpp b/src/hir/type.hpp
index 4b3692c0..d3aac4c6 100644
--- a/src/hir/type.hpp
+++ b/src/hir/type.hpp
@@ -96,6 +96,8 @@ struct TypeRef
     TypeRef() {}
     TypeRef(TypeRef&& ) = default;
     TypeRef(const TypeRef& ) = delete;
+    TypeRef& operator=(TypeRef&& ) = default;
+    TypeRef& operator=(const TypeRef&) = delete;
     
     TypeRef(::std::string name, unsigned int slot):
         m_data( Data::make_Generic({ mv$(name), slot }) )
diff --git a/src/hir/visitor.cpp b/src/hir/visitor.cpp
index 13fdd0f2..5734fb77 100644
--- a/src/hir/visitor.cpp
+++ b/src/hir/visitor.cpp
@@ -16,53 +16,66 @@ void ::HIR::Visitor::visit_crate(::HIR::Crate& crate)
     }
     for( auto& impl : crate.m_trait_impls )
     {
-        this->visit_trait_impl(impl.second);
+        this->visit_trait_impl(impl.first, impl.second);
     }
     for( auto& impl : crate.m_marker_impls )
     {
-        this->visit_marker_impl(impl.second);
+        this->visit_marker_impl(impl.first, impl.second);
     }
 }
 
 void ::HIR::Visitor::visit_module(::HIR::Module& mod)
 {
+    TRACE_FUNCTION;
     for( auto& named : mod.m_mod_items )
     {
+        const auto& name = named.first;
         auto& item = named.second->ent;
         TU_MATCH(::HIR::TypeItem, (item), (e),
         (Import, ),
         (Module,
+            DEBUG("mod " << name);
             this->visit_module(e);
             ),
         (TypeAlias,
+            DEBUG("type " << name);
             this->visit_type_alias(e);
             ),
         (Enum,
+            DEBUG("enum " << name);
             this->visit_enum(e);
             ),
         (Struct,
+            DEBUG("struct " << name);
             this->visit_struct(e);
             ),
         (Trait,
+            DEBUG("trait " << name);
             this->visit_trait(e);
             )
         )
     }
     for( auto& named : mod.m_value_items )
     {
+        const auto& name = named.first;
         auto& item = named.second->ent;
         TU_MATCH(::HIR::ValueItem, (item), (e),
-        (Import, ),
+        (Import,
+            // SimplePath - no visitor
+            ),
         (Constant,
+            DEBUG("const " << name);
             this->visit_constant(e);
             ),
         (Static,
+            DEBUG("static " << name);
             this->visit_static(e);
             ),
         (StructConstant,
             // Just a path
             ),
         (Function,
+            DEBUG("fn " << name);
             this->visit_function(e);
             ),
         (StructConstructor,
@@ -82,7 +95,7 @@ void ::HIR::Visitor::visit_type_impl(::HIR::TypeImpl& impl)
         this->visit_function(method.second);
     }
 }
-void ::HIR::Visitor::visit_trait_impl(::HIR::TraitImpl& impl)
+void ::HIR::Visitor::visit_trait_impl(const ::HIR::SimplePath& trait_path, ::HIR::TraitImpl& impl)
 {
     this->visit_params(impl.m_params);
     this->visit_path_params(impl.m_trait_args);
@@ -98,7 +111,7 @@ void ::HIR::Visitor::visit_trait_impl(::HIR::TraitImpl& impl)
         this->visit_type(ent.second);
     }
 }
-void ::HIR::Visitor::visit_marker_impl(::HIR::MarkerImpl& impl)
+void ::HIR::Visitor::visit_marker_impl(const ::HIR::SimplePath& trait_path, ::HIR::MarkerImpl& impl)
 {
     this->visit_params(impl.m_params);
     this->visit_path_params(impl.m_trait_args);
diff --git a/src/hir/visitor.hpp b/src/hir/visitor.hpp
index 7e8bcf63..ffeb7338 100644
--- a/src/hir/visitor.hpp
+++ b/src/hir/visitor.hpp
@@ -16,8 +16,8 @@ public:
     virtual void visit_module(::HIR::Module& mod);
     
     virtual void visit_type_impl(::HIR::TypeImpl& impl);
-    virtual void visit_trait_impl(::HIR::TraitImpl& impl);
-    virtual void visit_marker_impl(::HIR::MarkerImpl& impl);
+    virtual void visit_trait_impl(const ::HIR::SimplePath& trait_path, ::HIR::TraitImpl& impl);
+    virtual void visit_marker_impl(const ::HIR::SimplePath& trait_path, ::HIR::MarkerImpl& impl);
     
     // - Type Items
     virtual void visit_type_alias(::HIR::TypeAlias& item);
@@ -37,6 +37,8 @@ public:
     
     enum class PathContext {
         TYPE,
+        TRAIT,
+        
         VALUE,
     };
     virtual void visit_path(::HIR::Path& p, PathContext );
diff --git a/src/hir_conv/expand_type.cpp b/src/hir_conv/expand_type.cpp
index 6112e67d..0d8eb85e 100644
--- a/src/hir_conv/expand_type.cpp
+++ b/src/hir_conv/expand_type.cpp
@@ -35,6 +35,7 @@
         
         TU_MATCH_DEF( ::HIR::TypeItem, (it->second->ent), (e2),
         (
+            // Anything else - leave it be
             ),
         (TypeAlias,
             if( e2.m_params.m_types.size() > 0 ) {
@@ -75,6 +76,7 @@ public:
             auto new_type = ConvertHIR_ExpandAliases_GetExpansion(m_crate, e);
             if( ! new_type.m_data.is_Infer() ) {
                 DEBUG("Replacing " << ty << " with " << new_type);
+                ty = mv$(new_type);
             }
         )
     }
diff --git a/src/hir_conv/resolve_ufcs.cpp b/src/hir_conv/resolve_ufcs.cpp
index 6e61e8c4..fbc4bc6f 100644
--- a/src/hir_conv/resolve_ufcs.cpp
+++ b/src/hir_conv/resolve_ufcs.cpp
@@ -110,6 +110,7 @@ namespace {
                         }
                         // Found it, just keep going (don't care about details here)
                         } break;
+                    case ::HIR::Visitor::PathContext::TRAIT:
                     case ::HIR::Visitor::PathContext::TYPE: {
                         auto it1 = trait.m_types.find( e.item );
                         if( it1 == trait.m_types.end() ) {
@@ -154,6 +155,7 @@ namespace {
                         }
                         // Found it, just keep going (don't care about details here)
                         } break;
+                    case ::HIR::Visitor::PathContext::TRAIT:
                     case ::HIR::Visitor::PathContext::TYPE: {
                         continue ;
                         // Found it, just keep going (don't care about details here)
diff --git a/src/hir_typeck/main_bindings.hpp b/src/hir_typeck/main_bindings.hpp
new file mode 100644
index 00000000..07b0bd3f
--- /dev/null
+++ b/src/hir_typeck/main_bindings.hpp
@@ -0,0 +1,9 @@
+/*
+ */
+#pragma once
+
+namespace HIR {
+    class Crate;
+};
+
+extern void Typecheck_ModuleLevel(::HIR::Crate& crate);
diff --git a/src/hir_typeck/outer.cpp b/src/hir_typeck/outer.cpp
new file mode 100644
index 00000000..4ca789bb
--- /dev/null
+++ b/src/hir_typeck/outer.cpp
@@ -0,0 +1,186 @@
+/*
+ * Check types (and evaluate constants) at the module level
+ */
+#include <hir/hir.hpp>
+#include <hir/visitor.hpp>
+
+namespace {
+    
+    const ::HIR::GenericParams& get_params_for_item(const Span& sp, const ::HIR::Crate& crate, const ::HIR::SimplePath& path, ::HIR::Visitor::PathContext pc)
+    {
+        if( path.m_crate_name != "" )
+            TODO(sp, "get_params_for_item in crate");
+        
+        const ::HIR::Module* mod = &crate.m_root_module;
+        for( unsigned int i = 0; i < path.m_components.size() - 1; i ++ )
+        {
+            const auto& pc = path.m_components[i];
+            auto it = mod->m_mod_items.find( pc );
+            if( it == mod->m_mod_items.end() ) {
+                BUG(sp, "Couldn't find component " << i << " of " << path);
+            }
+            TU_MATCH_DEF( ::HIR::TypeItem, (it->second->ent), (e2),
+            (
+                BUG(sp, "Node " << i << " of path " << path << " wasn't a module");
+                ),
+            (Module,
+                mod = &e2;
+                )
+            )
+        }
+        
+        switch( pc )
+        {
+        case ::HIR::Visitor::PathContext::VALUE: {
+            auto it = mod->m_value_items.find( path.m_components.back() );
+            if( it == mod->m_value_items.end() ) {
+                BUG(sp, "Couldn't find final component of " << path);
+            }
+            
+            TU_MATCH( ::HIR::ValueItem, (it->second->ent), (e),
+            (Import,
+                BUG(sp, "Value path pointed to import");
+                ),
+            (Function,
+                return e.m_params;
+                ),
+            (Constant,
+                return e.m_params;
+                ),
+            (Static,
+                // TODO: Return an empty set?
+                BUG(sp, "Attepted to get parameters for static");
+                ),
+            (StructConstructor,
+                return get_params_for_item(sp, crate, e.ty, ::HIR::Visitor::PathContext::TYPE);
+                ),
+            (StructConstant,
+                return get_params_for_item(sp, crate, e.ty, ::HIR::Visitor::PathContext::TYPE);
+                )
+            )
+            } break;
+        case ::HIR::Visitor::PathContext::TRAIT:
+            // TODO: treat PathContext::TRAIT differently
+        case ::HIR::Visitor::PathContext::TYPE: {
+            auto it = mod->m_mod_items.find( path.m_components.back() );
+            if( it == mod->m_mod_items.end() ) {
+                BUG(sp, "Couldn't find final component of " << path);
+            }
+            
+            TU_MATCH( ::HIR::TypeItem, (it->second->ent), (e),
+            (Import,
+                BUG(sp, "Type path pointed to import - " << path);
+                ),
+            (TypeAlias,
+                BUG(sp, "Type path pointed to type alias - " << path);
+                ),
+            (Module,
+                BUG(sp, "Type path pointed to module - " << path);
+                ),
+            (Struct,
+                return e.m_params;
+                ),
+            (Enum,
+                return e.m_params;
+                ),
+            (Trait,
+                return e.m_params;
+                )
+            )
+            } break;
+        }
+        throw "";
+        
+    }
+    
+    class Visitor:
+        public ::HIR::Visitor
+    {
+        ::HIR::Crate& crate;
+        
+        ::HIR::GenericParams*   m_impl_generics;
+        ::HIR::GenericParams*   m_item_generics;
+    public:
+        Visitor(::HIR::Crate& crate):
+            crate(crate),
+            m_impl_generics(nullptr),
+            m_item_generics(nullptr)
+        {
+        }
+        
+        void visit_generic_path(::HIR::GenericPath& p, PathContext pc) override
+        {
+            const auto& params = get_params_for_item(Span(), crate, p.m_path, pc);
+            auto& args = p.m_params;
+            
+            if( args.m_types.size() == 0 && params.m_types.size() > 0 ) {
+                args.m_types.resize( params.m_types.size() );
+                DEBUG("- Insert inferrence");
+            }
+            DEBUG("p = " << p);
+        }
+        void visit_path(::HIR::Path& p, ::HIR::Visitor::PathContext pc) override
+        {
+            assert(pc == ::HIR::Visitor::PathContext::TYPE);
+            TU_MATCH(::HIR::Path::Data, (p.m_data), (e),
+            (Generic,
+                this->visit_generic_path(e, pc);
+                ),
+            (UfcsKnown,
+                this->visit_type(*e.type);
+                this->visit_generic_path(e.trait, ::HIR::Visitor::PathContext::TYPE);
+                // TODO: Locate impl block and check parameters
+                ),
+            (UfcsInherent,
+                this->visit_type(*e.type);
+                // TODO: Locate impl block and check parameters
+                ),
+            (UfcsUnknown,
+                BUG(Span(), "Encountered unknown-trait UFCS path during outer typeck");
+                )
+            )
+        }
+        
+        void visit_type_impl(::HIR::TypeImpl& impl) override
+        {
+            TRACE_FUNCTION_F("impl " << impl.m_type);
+            assert(m_impl_generics == nullptr);
+            m_impl_generics = &impl.m_params;
+            
+            ::HIR::Visitor::visit_type_impl(impl);
+            // Check that the type is valid
+            
+            m_impl_generics = nullptr;
+        }
+        void visit_trait_impl(const ::HIR::SimplePath& trait_path, ::HIR::TraitImpl& impl) override
+        {
+            TRACE_FUNCTION_F("impl " << trait_path << " for " << impl.m_type);
+            assert(m_impl_generics == nullptr);
+            m_impl_generics = &impl.m_params;
+            
+            ::HIR::Visitor::visit_trait_impl(trait_path, impl);
+            // Check that the type+trait is valid
+            
+            m_impl_generics = nullptr;
+        }
+        void visit_marker_impl(const ::HIR::SimplePath& trait_path, ::HIR::MarkerImpl& impl)
+        {
+            TRACE_FUNCTION_F("impl " << trait_path << " for " << impl.m_type << " { }");
+            assert(m_impl_generics == nullptr);
+            m_impl_generics = &impl.m_params;
+            
+            ::HIR::Visitor::visit_marker_impl(trait_path, impl);
+            // Check that the type+trait is valid
+            
+            m_impl_generics = nullptr;
+        }
+    };
+}
+
+
+void Typecheck_ModuleLevel(::HIR::Crate& crate)
+{
+    Visitor v { crate };
+    v.visit_crate(crate);
+}
+
diff --git a/src/main.cpp b/src/main.cpp
index bc22654c..d8384184 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -16,6 +16,7 @@
 #include <main_bindings.hpp>

 #include "resolve/main_bindings.hpp"

 #include "hir_conv/main_bindings.hpp"

+#include "hir_typeck/main_bindings.hpp"

 

 #include "expand/cfg.hpp"

 

@@ -26,8 +27,8 @@ bool debug_enabled()
 {

     //return true;

     //return g_cur_phase != "Parse";

-    //return g_cur_phase != "Parse" && g_cur_phase != "Expand";

-    return g_cur_phase != "Parse" && g_cur_phase != "Expand" && g_cur_phase != "Resolve";

+    return g_cur_phase != "Parse" && g_cur_phase != "Expand";

+    //return g_cur_phase != "Parse" && g_cur_phase != "Expand" && g_cur_phase != "Resolve";

 }

 ::std::ostream& debug_output(int indent, const char* function)

 {

@@ -157,26 +158,22 @@ int main(int argc, char *argv[])
         CompilePhaseV("Resolve UFCS paths", [&]() {

             ConvertHIR_ResolveUFCS(*hir_crate);

             });

-        

         CompilePhaseV("Constant Evaluate", [&]() {

             ConvertHIR_ConstantEvaluate(*hir_crate);

             });

         

-        // Typecheck / type propagate module (type annotations of all values)

-        // - Check all generic conditions (ensure referenced trait is valid)

-        //  > Binds the trait path to the actual trait definition

-        CompilePhaseV("TypecheckBounds", [&]() {

-            //Typecheck_GenericBounds(crate);

-            });

-        // - Check all generic parameters match required conditions (without doing full typeck)

-        //  > 

-        CompilePhaseV("TypecheckParams", [&]() {

-            //Typecheck_GenericParams(crate);

+        

+        // === Type checking ===

+        // - This can recurse and call the MIR lower to evaluate constants

+        

+        // Check outer items first (types of constants/functions/statics/impls/...)

+        // - Doesn't do any expressions except those in types

+        CompilePhaseV("Typecheck Outer", [&]() {

+            Typecheck_ModuleLevel(*hir_crate);

             });

-        // TODO: Evaluate all constants (or MIR them then evaluate)

-        // - Full function typeck

-        CompilePhaseV("TypecheckExpr", [&]() {

-            //Typecheck_Expr(crate);

+        // Check the rest of the expressions (including function bodies)

+        CompilePhaseV("Typecheck Expressions", [&]() {

+            //Typecheck_Expressions(*hir_crate);

             });

 

         if( params.last_stage == ProgramParams::STAGE_TYPECK ) {

@@ -184,6 +181,7 @@ int main(int argc, char *argv[])
         }

         

         // Expand closures into items

+        // - Now that all types are known, closures can be desugared

         CompilePhaseV("Lower Closures", [&]() {

             //ConvertHIR_Closures(hir_crate);

             });

diff --git a/src/parse/paths.cpp b/src/parse/paths.cpp
index a5d10f74..153f51a0 100644
--- a/src/parse/paths.cpp
+++ b/src/parse/paths.cpp
@@ -200,7 +200,7 @@ AST::Path Parse_Path(TokenStream& lex, bool is_abs, eParsePathGenericMode generi
     ::std::vector<TypeRef>  types;
     ::std::vector< ::std::string>   lifetimes;
     ::std::map< ::std::string, TypeRef> assoc_bounds;
-    ::std::vector<unsigned int> int_args;
+    //::std::vector<unsigned int> int_args;
     do {
         if( LOOK_AHEAD(lex) == TOK_GT || LOOK_AHEAD(lex) == TOK_DOUBLE_GT || LOOK_AHEAD(lex) == TOK_GTE || LOOK_AHEAD(lex) == TOK_DOUBLE_GT_EQUAL ) {
             GET_TOK(tok, lex);
diff --git a/src/resolve/absolute.cpp b/src/resolve/absolute.cpp
index 91176ee0..41eacd46 100644
--- a/src/resolve/absolute.cpp
+++ b/src/resolve/absolute.cpp
@@ -502,6 +502,7 @@ void Resolve_Absolute_Path_BindUFCS(Context& context, const Span& sp, Context::L
 }
 void Resolve_Absolute_Path_BindAbsolute(Context& context, const Span& sp, Context::LookupMode& mode, ::AST::Path& path)
 {
+    TRACE_FUNCTION_F("path = " << path);
     const auto& path_abs = path.m_class.as_Absolute();
     
     if( path_abs.crate != "" ) {
@@ -544,6 +545,7 @@ void Resolve_Absolute_Path_BindAbsolute(Context& context, const Span& sp, Contex
                 ERROR(sp, E0000, "Couldn't find path component '" << n.name() << "' of " << path);
             }
             const auto& name_ref = it->second;
+            DEBUG("#" << i << " \"" << n.name() << "\" = " << name_ref.path << (name_ref.is_import ? " (import)" : "") );
             
             TU_MATCH_DEF(::AST::PathBinding, (name_ref.path.binding()), (e),
             (
@@ -623,7 +625,9 @@ void Resolve_Absolute_Path_BindAbsolute(Context& context, const Span& sp, Contex
     }
     assert( ! tmp.binding().is_Unbound() );
     
-    path.bind( tmp.binding().clone() );
+    // Replaces the path with the one returned by `lookup_in_mod`, ensuring that `use` aliases are eliminated
+    DEBUG("Replace " << path << " with " << tmp);
+    path = mv$(tmp);
 }
 
 void Resolve_Absolute_Path(/*const*/ Context& context, const Span& sp, Context::LookupMode mode,  ::AST::Path& path)
@@ -676,7 +680,7 @@ void Resolve_Absolute_Path(/*const*/ Context& context, const Span& sp, Context::
         else {
             // Look up value
             auto p = context.lookup(sp, e.nodes[0].name(), mode);
-            DEBUG("Found val - " << p << " for " << path);
+            DEBUG("Found path " << p << " for " << path);
             path = mv$(p);
         }