HIR Expand - Add annotation pass

7 files changed, 447 insertions, 12 deletions

diff --git a/src/hir/expr.hpp b/src/hir/expr.hpp
index 203f878e..137377d7 100644
--- a/src/hir/expr.hpp
+++ b/src/hir/expr.hpp
@@ -11,6 +11,18 @@ namespace HIR {
 
 typedef ::std::vector< ::std::pair<const ::HIR::SimplePath*,const ::HIR::Trait*> >  t_trait_list;
 
+// Indicates how a result is used
+enum class ValueUsage {
+    // Not yet known (defalt state)
+    Unknown,
+    // Value is borrowed (shared)
+    Borrow,
+    // Value is mutated or uniquely borrowed
+    Mutate,
+    // Value is moved
+    Move,
+};
+
 class GenericParams;
 
 class ExprVisitor;
@@ -20,6 +32,7 @@ class ExprNode
 public:
     Span    m_span;
     ::HIR::TypeRef    m_res_type;
+    ValueUsage  m_usage = ValueUsage::Unknown;
 
     const Span& span() const { return m_span; }
     
diff --git a/src/hir_expand/annotate_value_usage.cpp b/src/hir_expand/annotate_value_usage.cpp
new file mode 100644
index 00000000..ea560bbc
--- /dev/null
+++ b/src/hir_expand/annotate_value_usage.cpp
@@ -0,0 +1,399 @@
+/*
+ * MRustC - Rust Compiler
+ * - By John Hodge (Mutabah/thePowersGang)
+ *
+ * hir_expand/annotate_value_usage.cpp
+ * - Marks _Variable, _Index, _Deref, and _Field nodes with how the result is used
+ */
+#include <hir/visitor.hpp>
+#include <hir/expr.hpp>
+#include <hir_typeck/static.hpp>
+#include <algorithm>
+#include "main_bindings.hpp"
+
+namespace {
+    
+    class ExprVisitor_Mark:
+        public ::HIR::ExprVisitor//Def
+    {
+        const StaticTraitResolve&    m_resolve;
+        ::std::vector< ::HIR::ValueUsage>   m_usage;
+        
+        struct UsageGuard
+        {
+            ExprVisitor_Mark& m_parent;
+            bool    m_pop;
+            UsageGuard(ExprVisitor_Mark& parent, bool pop):
+                m_parent(parent),
+                m_pop(pop)
+            {
+            }
+            ~UsageGuard()
+            {
+                if(m_pop) {
+                    m_parent.m_usage.pop_back();
+                }
+            }
+        };
+        
+        ::HIR::ValueUsage get_usage() const {
+            return (m_usage.empty() ? ::HIR::ValueUsage::Move : m_usage.back());
+        }
+        UsageGuard push_usage(::HIR::ValueUsage u) {
+            if( get_usage() == u ) {
+                return UsageGuard(*this, false);
+            }
+            else {
+                m_usage.push_back( u );
+                return UsageGuard(*this, true);
+            }
+        }
+        
+    public:
+        ExprVisitor_Mark(const StaticTraitResolve& resolve):
+            m_resolve(resolve)
+        {}
+        
+        void visit_root(::HIR::ExprPtr& root_ptr)
+        {
+            assert(root_ptr);
+            root_ptr->m_usage = this->get_usage();
+            auto expected_size = m_usage.size();
+            root_ptr->visit( *this );
+            assert( m_usage.size() == expected_size );
+        }
+        void visit_node_ptr(::HIR::ExprNodeP& node_ptr) override
+        {
+            assert(node_ptr);
+            node_ptr->m_usage = this->get_usage();
+            
+            auto expected_size = m_usage.size();
+            node_ptr->visit( *this );
+            assert( m_usage.size() == expected_size );
+        }
+        
+        void visit(::HIR::ExprNode_Block& node) override
+        {
+            auto _ = this->push_usage( ::HIR::ValueUsage::Move );
+            
+            for( auto& subnode : node.m_nodes ) {
+                this->visit_node_ptr(subnode);
+            }
+        }
+        
+        void visit(::HIR::ExprNode_Return& node) override
+        {
+            auto _ = this->push_usage( ::HIR::ValueUsage::Move );
+            this->visit_node_ptr( node.m_value );
+        }
+        void visit(::HIR::ExprNode_Let& node) override
+        {
+            if( node.m_value )
+            {
+                auto _ = this->push_usage( this->get_usage_for_pattern(node.m_pattern, node.m_type) );
+                this->visit_node_ptr( node.m_value );
+            }
+        }
+        void visit(::HIR::ExprNode_Loop& node) override
+        {
+            auto _ = this->push_usage( ::HIR::ValueUsage::Move );
+            this->visit_node_ptr( node.m_code );
+        }
+        void visit(::HIR::ExprNode_LoopControl& node) override
+        {
+            // NOTE: Leaf
+        }
+        void visit(::HIR::ExprNode_Match& node) override
+        {
+            {
+                const auto& val_ty = node.m_value->m_res_type;
+                ::HIR::ValueUsage   vu = ::HIR::ValueUsage::Unknown;
+                for( const auto& arm : node.m_arms )
+                {
+                    for( const auto& pat : arm.m_patterns ) 
+                        vu = ::std::max( vu, this->get_usage_for_pattern(pat, val_ty) );
+                }
+                auto _ = this->push_usage( vu );
+                this->visit_node_ptr( node.m_value );
+            }
+            
+            auto _ = this->push_usage( ::HIR::ValueUsage::Move );
+            for(auto& arm : node.m_arms)
+            {
+                if( arm.m_cond ) {
+                    this->visit_node_ptr( arm.m_cond );
+                }
+                this->visit_node_ptr( arm.m_code );
+            }
+        }
+        void visit(::HIR::ExprNode_If& node) override
+        {
+            auto _ = this->push_usage( ::HIR::ValueUsage::Move );
+            this->visit_node_ptr( node.m_cond );
+            this->visit_node_ptr( node.m_true );
+            if( node.m_false ) {
+                this->visit_node_ptr( node.m_false );
+            }
+        }
+        
+        void visit(::HIR::ExprNode_Assign& node) override
+        {
+            {
+                auto _ = this->push_usage( ::HIR::ValueUsage::Mutate );
+                this->visit_node_ptr(node.m_slot);
+            }
+            {
+                auto _ = this->push_usage( ::HIR::ValueUsage::Move );
+                this->visit_node_ptr(node.m_value);
+            }
+        }
+        void visit(::HIR::ExprNode_UniOp& node) override
+        {
+            switch(node.m_op)
+            {
+            case ::HIR::ExprNode_UniOp::Op::Invert:
+            case ::HIR::ExprNode_UniOp::Op::Negate:
+                m_usage.push_back( ::HIR::ValueUsage::Move );
+                break;
+            case ::HIR::ExprNode_UniOp::Op::Ref:
+                m_usage.push_back( ::HIR::ValueUsage::Borrow );
+                break;
+            case ::HIR::ExprNode_UniOp::Op::RefMut:
+                m_usage.push_back( ::HIR::ValueUsage::Mutate );
+                break;
+            }
+            
+            this->visit_node_ptr(node.m_value);
+            
+            m_usage.pop_back();
+        }
+        
+        void visit(::HIR::ExprNode_BinOp& node) override
+        {
+            switch(node.m_op)
+            {
+            case ::HIR::ExprNode_BinOp::Op::CmpEqu:
+            case ::HIR::ExprNode_BinOp::Op::CmpNEqu:
+            case ::HIR::ExprNode_BinOp::Op::CmpLt:
+            case ::HIR::ExprNode_BinOp::Op::CmpLtE:
+            case ::HIR::ExprNode_BinOp::Op::CmpGt:
+            case ::HIR::ExprNode_BinOp::Op::CmpGtE:
+                m_usage.push_back( ::HIR::ValueUsage::Borrow );
+                break;
+            default:
+                m_usage.push_back( ::HIR::ValueUsage::Move );
+                break;
+            }
+            
+            this->visit_node_ptr(node.m_left);
+            this->visit_node_ptr(node.m_right);
+            
+            m_usage.pop_back();
+        }
+        void visit(::HIR::ExprNode_Cast& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            this->visit_node_ptr(node.m_value);
+        }
+        void visit(::HIR::ExprNode_Unsize& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            this->visit_node_ptr(node.m_value);
+        }
+        void visit(::HIR::ExprNode_Index& node) override
+        {
+            // TODO: Override to ::Borrow if Res: Copy and moving
+            if( this->get_usage() == ::HIR::ValueUsage::Move && type_is_copy(node.m_res_type) ) {
+                auto _ = push_usage( ::HIR::ValueUsage::Borrow );
+                this->visit_node_ptr(node.m_value);
+            }
+            else {
+                this->visit_node_ptr(node.m_value);
+            }
+            
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            this->visit_node_ptr(node.m_index);
+        }
+        void visit(::HIR::ExprNode_Deref& node) override
+        {
+            if( this->get_usage() == ::HIR::ValueUsage::Move && type_is_copy(node.m_res_type) ) {
+                auto _ = push_usage( ::HIR::ValueUsage::Borrow );
+                this->visit_node_ptr(node.m_value);
+            }
+            else {
+                this->visit_node_ptr(node.m_value);
+            }
+        }
+        
+        void visit(::HIR::ExprNode_Field& node) override
+        {
+            // If taking this field by value, but the type is Copy - pretend it's a borrow.
+            if( this->get_usage() == ::HIR::ValueUsage::Move && type_is_copy(node.m_res_type) ) {
+                auto _ = push_usage( ::HIR::ValueUsage::Borrow );
+                this->visit_node_ptr(node.m_value);
+            }
+            else {
+                node.m_value->visit( *this );
+            }
+        }
+        
+        void visit(::HIR::ExprNode_TupleVariant& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            
+            for( auto& val : node.m_args )
+                this->visit_node_ptr(val);
+        }
+        void visit(::HIR::ExprNode_CallPath& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            
+            for( auto& val : node.m_args )
+                this->visit_node_ptr(val);
+        }
+        void visit(::HIR::ExprNode_CallValue& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            
+            this->visit_node_ptr(node.m_value);
+            for( auto& val : node.m_args )
+                this->visit_node_ptr(val);
+        }
+        void visit(::HIR::ExprNode_CallMethod& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            
+            this->visit_node_ptr(node.m_value);
+            for( auto& val : node.m_args )
+                this->visit_node_ptr(val);
+        }
+        
+        void visit(::HIR::ExprNode_Literal& node) override
+        {
+        }
+        void visit(::HIR::ExprNode_UnitVariant& node) override
+        {
+        }
+        void visit(::HIR::ExprNode_PathValue& node) override
+        {
+        }
+        void visit(::HIR::ExprNode_Variable& node) override
+        {
+        }
+
+        void visit(::HIR::ExprNode_StructLiteral& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            
+            if( node.m_base_value ) {
+                this->visit_node_ptr(node.m_base_value);
+            }
+            for( auto& fld_val : node.m_values ) {
+                this->visit_node_ptr(fld_val.second);
+            }
+        }
+        void visit(::HIR::ExprNode_Tuple& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            for( auto& val : node.m_vals ) {
+                this->visit_node_ptr(val);
+            }
+        }
+        void visit(::HIR::ExprNode_ArrayList& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            for( auto& val : node.m_vals ) {
+                this->visit_node_ptr(val);
+            }
+        }
+        void visit(::HIR::ExprNode_ArraySized& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            this->visit_node_ptr(node.m_val);
+        }
+        
+        void visit(::HIR::ExprNode_Closure& node) override
+        {
+            auto _ = push_usage( ::HIR::ValueUsage::Move );
+            this->visit_node_ptr(node.m_code);
+        }
+        
+    private:
+        ::HIR::ValueUsage get_usage_for_pattern( const ::HIR::Pattern& pat, const ::HIR::TypeRef& ty ) const
+        {
+            // TODO: Detect if a by-value binding exists for a non-Copy type
+            return ::HIR::ValueUsage::Move;
+        }
+        
+        bool type_is_copy(const ::HIR::TypeRef& ty) const
+        {
+            return m_resolve.type_is_copy(ty);
+        }
+    };
+
+    
+    class OuterVisitor:
+        public ::HIR::Visitor
+    {
+        StaticTraitResolve   m_resolve;
+    public:
+        OuterVisitor(const ::HIR::Crate& crate):
+            m_resolve(crate)
+        {}
+        
+        void visit_expr(::HIR::ExprPtr& exp) override {
+            if( exp )
+            {
+                ExprVisitor_Mark    ev { m_resolve };
+                ev.visit_root( exp );
+            }
+        }
+        
+        // ------
+        // Code-containing items
+        // ------
+        void visit_function(::HIR::ItemPath p, ::HIR::Function& item) override {
+            auto _ = this->m_resolve.set_item_generics(item.m_params);
+            ::HIR::Visitor::visit_function(p, item);
+        }
+        void visit_static(::HIR::ItemPath p, ::HIR::Static& item) override {
+            // NOTE: No generics
+            ::HIR::Visitor::visit_static(p, item);
+        }
+        void visit_constant(::HIR::ItemPath p, ::HIR::Constant& item) override {
+            // NOTE: No generics
+            ::HIR::Visitor::visit_constant(p, item);
+        }
+        void visit_enum(::HIR::ItemPath p, ::HIR::Enum& item) override {
+            auto _ = this->m_resolve.set_item_generics(item.m_params);
+            ::HIR::Visitor::visit_enum(p, item);
+        }
+        
+        
+        void visit_trait(::HIR::ItemPath p, ::HIR::Trait& item) override {
+            auto _ = this->m_resolve.set_impl_generics(item.m_params);
+            ::HIR::Visitor::visit_trait(p, item);
+        }
+        
+        void visit_type_impl(::HIR::TypeImpl& impl) override
+        {
+            TRACE_FUNCTION_F("impl " << impl.m_type);
+            auto _ = this->m_resolve.set_impl_generics(impl.m_params);
+            
+            ::HIR::Visitor::visit_type_impl(impl);
+        }
+        void visit_trait_impl(const ::HIR::SimplePath& trait_path, ::HIR::TraitImpl& impl) override
+        {
+            TRACE_FUNCTION_F("impl " << trait_path << " for " << impl.m_type);
+            auto _ = this->m_resolve.set_impl_generics(impl.m_params);
+            
+            ::HIR::Visitor::visit_trait_impl(trait_path, impl);
+        }
+    };
+}
+
+void HIR_Expand_AnnotateUsage(::HIR::Crate& crate)
+{
+    OuterVisitor    ov(crate);
+    ov.visit_crate( crate );
+}
diff --git a/src/hir_expand/closures.cpp b/src/hir_expand/closures.cpp
index 5ce07886..0ede24bd 100644
--- a/src/hir_expand/closures.cpp
+++ b/src/hir_expand/closures.cpp
@@ -636,17 +636,7 @@ namespace {
     private:
         bool type_is_copy(const ::HIR::TypeRef& ty) const
         {
-            TU_MATCH_DEF(::HIR::TypeRef::Data, (ty.m_data), (e),
-            (
-                return false;
-                ),
-            (Primitive,
-                return e != ::HIR::CoreType::Str;
-                ),
-            (Array,
-                return type_is_copy(*e.inner);
-                )
-            )
+            return m_resolve.type_is_copy(ty);
         }
         
         void add_closure_def(unsigned int slot)
diff --git a/src/hir_expand/main_bindings.hpp b/src/hir_expand/main_bindings.hpp
index 525396a2..085673fe 100644
--- a/src/hir_expand/main_bindings.hpp
+++ b/src/hir_expand/main_bindings.hpp
@@ -6,5 +6,6 @@ namespace HIR {
     class Crate;
 };
 
+extern void HIR_Expand_AnnotateUsage(::HIR::Crate& crate);
 extern void HIR_Expand_Closures(::HIR::Crate& crate);
 extern void HIR_Expand_UfcsEverything(::HIR::Crate& crate);
diff --git a/src/hir_typeck/static.cpp b/src/hir_typeck/static.cpp
index d987f682..8320c58e 100644
--- a/src/hir_typeck/static.cpp
+++ b/src/hir_typeck/static.cpp
@@ -547,6 +547,28 @@ bool StaticTraitResolve::trait_contains_type(const Span& sp, const ::HIR::Generi
     return false;
 }
 
+bool StaticTraitResolve::type_is_copy(const ::HIR::TypeRef& ty) const
+{
+    TU_MATCH_DEF(::HIR::TypeRef::Data, (ty.m_data), (e),
+    (
+        // Search for a Copy bound or impl.
+        return false;
+        ),
+    (Borrow,
+        return (e.type == ::HIR::BorrowType::Shared);
+        ),
+    (Pointer,
+        return true;
+        ),
+    (Primitive,
+        return e != ::HIR::CoreType::Str;
+        ),
+    (Array,
+        return type_is_copy(*e.inner);
+        )
+    )
+}
+
 bool ImplRef::more_specific_than(const ImplRef& other) const
 {
     TU_MATCH(Data, (this->m_data), (te),
diff --git a/src/hir_typeck/static.hpp b/src/hir_typeck/static.hpp
index f2ca411d..8d4046a8 100644
--- a/src/hir_typeck/static.hpp
+++ b/src/hir_typeck/static.hpp
@@ -94,5 +94,11 @@ public:
             ) const;
     /// 
     bool 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;
+    
+    
+    // --------------
+    // Common bounds
+    // -------------
+    bool type_is_copy(const ::HIR::TypeRef& ty) const;
 };
 
diff --git a/src/main.cpp b/src/main.cpp
index 1ca3f5e9..453a420a 100644
--- a/src/main.cpp
+++ b/src/main.cpp
@@ -189,6 +189,11 @@ int main(int argc, char *argv[])
         CompilePhaseV("Typecheck Expressions", [&]() {

             Typecheck_Expressions(*hir_crate);

             });

+        // === HIR Expansion ===

+        // Annotate how each node's result is used

+        CompilePhaseV("Expand HIR Annotate", [&]() {

+            HIR_Expand_AnnotateUsage(*hir_crate);

+            });

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

         CompilePhaseV("Expand HIR Closures", [&]() {

             HIR_Expand_Closures(*hir_crate);

@@ -206,7 +211,6 @@ int main(int argc, char *argv[])
             return 0;

         }

         

-        // Expand closures into items

         // Lower expressions into MIR

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

             HIR_GenerateMIR(*hir_crate);