Macros - Planning of more efficient macro_rules evaluation

1 files changed, 306 insertions, 0 deletions

diff --git a/src/parse/macro_rules.cpp b/src/parse/macro_rules.cpp
index 11a4ab4e..94f55e2d 100644
--- a/src/parse/macro_rules.cpp
+++ b/src/parse/macro_rules.cpp
@@ -223,6 +223,243 @@ MacroRule Parse_MacroRules_Var(TokenStream& lex)
     return rule;
 }
 
+struct UnifiedPatFrag
+{
+    ::std::vector<MacroPatEnt>  m_pats_ents;
+    unsigned int    m_pattern_end;
+    ::std::vector< UnifiedPatFrag >  m_next_frags;
+    
+    UnifiedPatFrag():
+        m_pattern_end(~0)
+    {}
+    
+    UnifiedPatFrag split_at(unsigned int remaining_count) {
+        UnifiedPatFrag  rv;
+        for(unsigned int i = remaining_count; i < m_pats_ents.size(); i ++)
+            rv.m_pats_ents.push_back( mv$(m_pats_ents[i]) );
+        m_pats_ents.resize(remaining_count);
+        rv.m_pattern_end = m_pattern_end;   m_pattern_end = ~0;
+        rv.m_next_frags = mv$(m_next_frags);
+        return rv;
+    }
+};
+
+struct UnifiedMacroRules
+{
+    UnifiedPatFrag  m_pattern;
+};
+
+bool is_token_path(eTokenType tt) {
+    switch(tt)
+    {
+    case TOK_IDENT:
+    case TOK_DOUBLE_COLON:
+    case TOK_LT:
+    case TOK_DOUBLE_LT:
+    case TOK_RWORD_SELF:
+    case TOK_RWORD_SUPER:
+        return true;
+    default:
+        return false;
+    }
+}
+bool is_token_pat(eTokenType tt) {
+    if( is_token_path(tt) )
+        return true;
+    switch( tt )
+    {
+    case TOK_PAREN_OPEN:
+    case TOK_SQUARE_OPEN:
+    
+    case TOK_AMP:
+    case TOK_RWORD_BOX:
+    case TOK_RWORD_REF:
+    case TOK_RWORD_MUT:
+    case TOK_STRING:
+    case TOK_INTEGER:
+    case TOK_CHAR:
+        return true;
+    default:
+        return false;
+    }
+}
+bool is_token_type(eTokenType tt) {
+    if( is_token_path(tt) )
+        return true;
+    switch( tt )
+    {
+    case TOK_PAREN_OPEN:
+    case TOK_SQUARE_OPEN:
+    case TOK_STAR:
+    case TOK_AMP:
+        return true;
+    default:
+        return false;
+    }
+}
+bool is_token_expr(eTokenType tt) {
+    if( is_token_path(tt) )
+        return true;
+    switch( tt )
+    {
+    case TOK_AMP:
+    case TOK_STAR:
+    case TOK_PAREN_OPEN:
+    case TOK_MACRO:
+    case TOK_DASH:
+    
+    case TOK_INTEGER:
+    case TOK_STRING:
+        return true;
+    default:
+        return false;
+    }
+}
+
+bool patterns_are_same(const Span& sp, const MacroPatEnt& left, const MacroPatEnt& right)
+{
+    if( left.type > right.type )
+        return patterns_are_same(sp, right, left);
+    
+    // NOTE: left.type <= right.type
+    switch(right.type)
+    {
+    case MacroPatEnt::PAT_TOKEN:
+        assert( left.type == MacroPatEnt::PAT_TOKEN );
+        return right.tok == left.tok;
+    case MacroPatEnt::PAT_LOOP:
+        switch(left.type)
+        {
+        case MacroPatEnt::PAT_TOKEN:
+            // - Check for compatibility, but these two don't match
+            if( patterns_are_same(sp, left, right.subpats.at(0)) == true )
+                ERROR(sp, E0000, "Incompatible use of loop with matching non-loop");
+            return false;
+        case MacroPatEnt::PAT_LOOP:
+            TODO(sp, "patterns_are_same - PAT_LOOP");
+        default:
+            assert( !"" );
+        }
+    
+    case MacroPatEnt::PAT_TT:
+        if( left.type == right.type )
+            return true;
+        ERROR(sp, E0000, "Incompatible macro fragments - " << right << " used with " << left);
+        break;
+    
+    case MacroPatEnt::PAT_PAT:
+        switch(left.type)
+        {
+        case MacroPatEnt::PAT_TOKEN:
+            // - If this token is a valid pattern token, error
+            if( is_token_pat(left.tok.type()) )
+                ERROR(sp, E0000, "Incompatible macro fragments - " << right << " used with " << left);
+            return false;
+        case MacroPatEnt::PAT_PAT:
+            return true;
+        default:
+            ERROR(sp, E0000, "Incompatible macro fragments - " << right << " used with " << left);
+        }
+        break;
+    // `:ident` - Compatible with just other tokens
+    case MacroPatEnt::PAT_IDENT:
+        switch(left.type)
+        {
+        case MacroPatEnt::PAT_TOKEN:
+            if( left.tok.type() == TOK_IDENT )
+                ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+            return false;
+        case MacroPatEnt::PAT_IDENT:
+            return true;
+        default:
+            ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+        }
+    case MacroPatEnt::PAT_PATH:
+        switch(left.type)
+        {
+        case MacroPatEnt::PAT_TOKEN:
+            if( is_token_path(left.tok.type()) )
+                ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+            return false;
+        case MacroPatEnt::PAT_PATH:
+            return true;
+        default:
+            ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+        }
+    case MacroPatEnt::PAT_TYPE:
+        switch(left.type)
+        {
+        case MacroPatEnt::PAT_TOKEN:
+            if( is_token_type(left.tok.type()) )
+                ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+            return false;
+        case MacroPatEnt::PAT_TYPE:
+            return true;
+        default:
+            ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+        }
+    case MacroPatEnt::PAT_EXPR:
+        switch(left.type)
+        {
+        case MacroPatEnt::PAT_TOKEN:
+            if( is_token_expr(left.tok.type()) )
+                ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+            return false;
+        case MacroPatEnt::PAT_EXPR:
+            return true;
+        default:
+            ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+        }
+    case MacroPatEnt::PAT_STMT:
+        switch(left.type)
+        {
+        case MacroPatEnt::PAT_TOKEN:
+            switch(left.tok.type())
+            {
+            case TOK_BRACE_OPEN:
+            case TOK_RWORD_LET:
+                ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+            default:
+                if( is_token_expr(left.tok.type()) )
+                    ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+                return false;
+            }
+        case MacroPatEnt::PAT_STMT:
+            return true;
+        default:
+            ERROR(sp, E0000, "Incompatible macro fragments " << right << " used with " << left);
+        }
+    // Block - Expects '{' - Compatible with everything but a literal '{'
+    case MacroPatEnt::PAT_BLOCK:
+        switch(left.type)
+        {
+        case MacroPatEnt::PAT_TOKEN:
+            if( left.tok.type() == TOK_BRACE_OPEN )
+                ERROR(sp, E0000, "Incompatible macro fragments");
+            return false;
+        case MacroPatEnt::PAT_BLOCK:
+            return true;
+        default:
+            return false;
+        }
+    // Matches meta/attribute fragments.
+    // - Compatible with everythin but a literal #[ token
+    case MacroPatEnt::PAT_META:
+        switch(left.type)
+        {
+        case MacroPatEnt::PAT_TOKEN:
+            if( left.tok.type() == TOK_ATTR_OPEN )
+                ERROR(sp, E0000, "Incompatible macro fragments");
+            return false;
+        case MacroPatEnt::PAT_META:
+            return true;
+        default:
+            return false;
+        }
+    }
+    throw "";
+}
+
 MacroRules Parse_MacroRules(TokenStream& lex)
 {
     TRACE_FUNCTION_F("");
@@ -241,5 +478,74 @@ MacroRules Parse_MacroRules(TokenStream& lex)
         }
     }
     
+    UnifiedPatFrag  root_frag;
+    
+    // Re-parse the patterns into a unified form
+    for(unsigned int rule_idx = 0; rule_idx < rules.size(); rule_idx ++)
+    {
+        const auto& rule = rules[rule_idx];
+        
+        UnifiedPatFrag* cur_frag = &root_frag;
+        unsigned int    frag_ofs = 0;
+        for( const auto& pat : rule.m_pattern )
+        {
+            Span    sp(pat.tok.get_pos());
+            
+            if( frag_ofs == cur_frag->m_pats_ents.size() ) {
+                if( cur_frag->m_pattern_end == ~0u && cur_frag->m_next_frags.size() == 0 ) {
+                    cur_frag->m_pats_ents.push_back( pat );
+                    frag_ofs += 1;
+                }
+                else {
+                    // Check if any of the other paths match
+                    bool found = false;
+                    for( auto& next_frag : cur_frag->m_next_frags ) {
+                        assert( next_frag.m_pats_ents.size() > 0 );
+                        if( patterns_are_same( Span(pat.tok.get_pos()), next_frag.m_pats_ents[0], pat ) ) {
+                            found = true;
+                            cur_frag = &next_frag;
+                            break;
+                        }
+                    }
+                    // If not, create a new frag
+                    if( ! found ) {
+                        cur_frag->m_next_frags.push_back( UnifiedPatFrag() );
+                        cur_frag = &cur_frag->m_next_frags.back();
+                        cur_frag->m_pats_ents.push_back( pat );
+                    }
+                    frag_ofs = 1;
+                }
+            }
+            else if( ! patterns_are_same(sp, cur_frag->m_pats_ents[frag_ofs], pat) ) {
+                // Difference, split the block.
+                auto new_frag = cur_frag->split_at(frag_ofs);
+                assert( cur_frag->m_next_frags.size() == 0 );
+                cur_frag->m_next_frags.push_back( mv$(new_frag) );
+                
+                // - Update cur_frag to a newly pushed fragment, and push this pattern to it
+                cur_frag->m_next_frags.push_back( UnifiedPatFrag() );
+                cur_frag = &cur_frag->m_next_frags.back();
+                cur_frag->m_pats_ents.push_back( pat );
+                frag_ofs = 1;
+            }
+            else {
+                // Matches - Keep going
+                frag_ofs += 1;
+            }
+        }
+        
+        // If this pattern ended before the current fragment ended
+        if( frag_ofs < cur_frag->m_pats_ents.size() ) {
+            // Split the current fragment
+            auto new_frag = cur_frag->split_at(frag_ofs);
+            assert( cur_frag->m_next_frags.size() == 0 );
+            cur_frag->m_next_frags.push_back( mv$(new_frag) );
+            // Keep cur_frag the same
+        }
+        cur_frag->m_pattern_end = rule_idx;
+    }
+    
+    // TODO: use `root_frag` above for the actual evaluation
+    
     return MacroRules( mv$(rules) );
 }