From d285e8790724f95d39e1cb2a1a7fc9e30aa88fda Mon Sep 17 00:00:00 2001 From: John Hodge Date: Fri, 7 Oct 2016 23:49:56 +0800 Subject: MIR Gen Match - (minor) Sort code a little bit --- src/mir/from_hir_match.cpp | 2177 ++++++++++++++++++++++---------------------- 1 file changed, 1090 insertions(+), 1087 deletions(-) (limited to 'src/mir/from_hir_match.cpp') diff --git a/src/mir/from_hir_match.cpp b/src/mir/from_hir_match.cpp index 72c4b5f9..cb726246 100644 --- a/src/mir/from_hir_match.cpp +++ b/src/mir/from_hir_match.cpp @@ -185,9 +185,10 @@ void MIR_LowerHIR_Match( MirBuilder& builder, MirConverter& conv, ::HIR::ExprNod arm_code.push_back( mv$(ac) ); } + // Sort columns of `arm_rules` to maximise effectiveness if( arm_rules[0].m_rules.size() > 1 ) { - // TODO: Sort columns of `arm_rules` to maximise effectiveness + // TODO: Should columns be sorted within equal sub-arms too? ::std::vector column_weights( arm_rules[0].m_rules.size() ); for(const auto& arm_rule : arm_rules) { @@ -238,1256 +239,1258 @@ void MIR_LowerHIR_Match( MirBuilder& builder, MirConverter& conv, ::HIR::ExprNod } // -------------------------------------------------------------------- -// Dumb and Simple +// Common Code - Pattern Rules // -------------------------------------------------------------------- -int MIR_LowerHIR_Match_Simple__GeneratePattern(MirBuilder& builder, const Span& sp, const PatternRule* rules, unsigned int num_rules, const ::HIR::TypeRef& ty, const ::MIR::LValue& match_val, ::MIR::BasicBlockId fail_bb); +::std::ostream& operator<<(::std::ostream& os, const PatternRule& x) +{ + os <<"{"; + for(const auto idx : x.field_path) + os << "." << static_cast(idx); + os << "}="; + TU_MATCHA( (x), (e), + (Any, + os << "_"; + ), + // Enum variant + (Variant, + os << e.idx << " [" << e.sub_rules << "]"; + ), + // Enum variant + (Slice, + os << "len=" << e.len << " [" << e.sub_rules << "]"; + ), + // Boolean (different to Constant because of how restricted it is) + (Bool, + os << (e ? "true" : "false"); + ), + // General value + (Value, + os << e; + ), + (ValueRange, + os << e.first << " ... " << e.last; + ) + ) + return os; +} -void MIR_LowerHIR_Match_Simple( MirBuilder& builder, MirConverter& conv, ::HIR::ExprNode_Match& node, ::MIR::LValue match_val, t_arm_rules arm_rules, ::std::vector arms_code, ::MIR::BasicBlockId first_cmp_block ) +::Ordering PatternRuleset::rule_is_before(const PatternRule& l, const PatternRule& r) { - TRACE_FUNCTION; + if( l.tag() != r.tag() ) { + // Any comes last, don't care about rest + if( l.tag() < r.tag() ) + return ::OrdGreater; + else + return ::OrdLess; + } - // 1. Generate pattern matches - unsigned int rule_idx = 0; - builder.set_cur_block( first_cmp_block ); - for( unsigned int arm_idx = 0; arm_idx < node.m_arms.size(); arm_idx ++ ) - { - const auto& arm = node.m_arms[arm_idx]; - auto& arm_code = arms_code[arm_idx]; - - auto next_arm_bb = builder.new_bb_unlinked(); - - for( unsigned int i = 0; i < arm.m_patterns.size(); i ++ ) + TU_MATCHA( (l,r), (le,re), + (Any, + return ::OrdEqual; + ), + (Variant, + if( le.idx != re.idx ) + return ::ord(le.idx, re.idx); + assert( le.sub_rules.size() == re.sub_rules.size() ); + for(unsigned int i = 0; i < le.sub_rules.size(); i ++) { - const auto& pat_rule = arm_rules[rule_idx]; - bool is_last_pat = (i+1 == arm.m_patterns.size()); - auto next_pattern_bb = (!is_last_pat ? builder.new_bb_unlinked() : next_arm_bb); - - // 1. Check - // - If the ruleset is empty, this is a _ arm over a value - if( pat_rule.m_rules.size() > 0 ) - { - MIR_LowerHIR_Match_Simple__GeneratePattern(builder, arm.m_code->span(), pat_rule.m_rules.data(), pat_rule.m_rules.size(), node.m_value->m_res_type, match_val, next_pattern_bb); - } - builder.end_block( ::MIR::Terminator::make_Goto(arm_code.destructures[i]) ); - builder.set_cur_block( arm_code.destructures[i] ); - - // - Go to code/condition check - if( arm_code.has_condition ) - { - builder.end_block( ::MIR::Terminator::make_Goto(arm_code.cond_start) ); - } - else - { - builder.end_block( ::MIR::Terminator::make_Goto(arm_code.code) ); - } - - if( !is_last_pat ) - { - builder.set_cur_block( next_pattern_bb ); - } - - rule_idx ++; + auto cmp = rule_is_before(le.sub_rules[i], re.sub_rules[i]); + if( cmp != ::OrdEqual ) + return cmp; } - if( arm_code.has_condition ) + return ::OrdEqual; + ), + (Slice, + if( le.len != re.len ) + return ::ord(le.len, re.len); + // Wait? Why would the rule count be the same? + assert( le.sub_rules.size() == re.sub_rules.size() ); + for(unsigned int i = 0; i < le.sub_rules.size(); i ++) { - builder.set_cur_block( arm_code.cond_end ); - builder.end_block( ::MIR::Terminator::make_If({ mv$(arm_code.cond_lval), arm_code.code, next_arm_bb }) ); + auto cmp = rule_is_before(le.sub_rules[i], re.sub_rules[i]); + if( cmp != ::OrdEqual ) + return cmp; } - builder.set_cur_block( next_arm_bb ); + return ::OrdEqual; + ), + (Bool, + return ::ord( le, re ); + ), + (Value, + TODO(Span(), "Order PatternRule::Value"); + ), + (ValueRange, + TODO(Span(), "Order PatternRule::ValueRange"); + ) + ) + throw ""; +} + +bool PatternRuleset::is_before(const PatternRuleset& other) const +{ + assert( m_rules.size() == other.m_rules.size() ); + for(unsigned int i = 0; i < m_rules.size(); i ++) + { + const auto& l = m_rules[i]; + const auto& r = other.m_rules[i]; + auto cmp = rule_is_before(l, r); + if( cmp != ::OrdEqual ) + return cmp == ::OrdLess; } - // - Kill the final pattern block (which is dead code) - builder.end_block( ::MIR::Terminator::make_Diverge({}) ); + return false; } -int MIR_LowerHIR_Match_Simple__GeneratePattern(MirBuilder& builder, const Span& sp, const PatternRule* rules, unsigned int num_rules, const ::HIR::TypeRef& ty, const ::MIR::LValue& match_val, ::MIR::BasicBlockId fail_bb) + +void PatternRulesetBuilder::push_rule(PatternRule r) { - TRACE_FUNCTION_F("ty = " << ty); - assert( num_rules > 0 ); - const auto& rule = *rules; - TU_MATCHA( (ty.m_data), (te), - (Infer, - BUG(sp, "Hit _ in type - " << ty); - ), - (Diverge, - BUG(sp, "Matching over !"); - ), + m_rules.push_back( mv$(r) ); + m_rules.back().field_path = m_field_path; +} + +void PatternRulesetBuilder::append_from(const Span& sp, const ::HIR::Pattern& pat, const ::HIR::TypeRef& ty) +{ + TRACE_FUNCTION_F("pat="<m_value_res.as_Integer(); + ) + ) + throw ""; + } + static double get_pattern_value_float(const Span& sp, const ::HIR::Pattern& pat, const ::HIR::Pattern::Value& val) { + TU_MATCH_DEF( ::HIR::Pattern::Value, (val), (e), + ( + BUG(sp, "Invalid Value type in " << pat); + ), + (Float, + return e.value; + ), + (Named, + assert(e.binding); + return e.binding->m_value_res.as_Float(); + ) + ) + throw ""; + } + }; + + TU_MATCHA( (ty.m_data), (e), + (Infer, BUG(sp, "Ivar for in match type"); ), + (Diverge, BUG(sp, "Diverge in match type"); ), (Primitive, - if( !rule.is_Any() ) { - switch(te) + TU_MATCH_DEF(::HIR::Pattern::Data, (pat.m_data), (pe), + ( BUG(sp, "Matching primitive with invalid pattern - " << pat); ), + (Any, + this->push_rule( PatternRule::make_Any({}) ); + ), + (Range, + switch(e) { - case ::HIR::CoreType::Bool: { - ASSERT_BUG(sp, rule.is_Bool(), "PatternRule for bool isn't _Bool"); - bool test_val = rule.as_Bool(); - - auto succ_bb = builder.new_bb_unlinked(); - - if( test_val ) { - builder.end_block( ::MIR::Terminator::make_If({ match_val.clone(), succ_bb, fail_bb }) ); - } - else { - builder.end_block( ::MIR::Terminator::make_If({ match_val.clone(), fail_bb, succ_bb }) ); - } - builder.set_cur_block(succ_bb); + case ::HIR::CoreType::F32: + case ::HIR::CoreType::F64: { + double start = H::get_pattern_value_float(sp, pat, pe.start); + double end = H::get_pattern_value_float(sp, pat, pe.end ); + this->push_rule( PatternRule::make_ValueRange( {::MIR::Constant(start), ::MIR::Constant(end)} ) ); } break; case ::HIR::CoreType::U8: case ::HIR::CoreType::U16: case ::HIR::CoreType::U32: case ::HIR::CoreType::U64: - case ::HIR::CoreType::Usize: - TU_MATCH_DEF( PatternRule, (rule), (re), - ( - BUG(sp, "PatternRule for integer is not Value or ValueRange"); - ), - (Value, - auto succ_bb = builder.new_bb_unlinked(); - - auto test_lval = builder.lvalue_or_temp(sp, te, ::MIR::Constant(re.as_Uint())); - auto cmp_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::EQ, mv$(test_lval) })); - builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_lval), succ_bb, fail_bb }) ); - builder.set_cur_block(succ_bb); - ), - (ValueRange, - TODO(sp, "Simple match over primitive - " << ty << " - ValueRange"); - ) - ) - break; + case ::HIR::CoreType::Usize: { + uint64_t start = H::get_pattern_value_int(sp, pat, pe.start); + uint64_t end = H::get_pattern_value_int(sp, pat, pe.end ); + this->push_rule( PatternRule::make_ValueRange( {::MIR::Constant(start), ::MIR::Constant(end)} ) ); + } break; case ::HIR::CoreType::I8: case ::HIR::CoreType::I16: case ::HIR::CoreType::I32: case ::HIR::CoreType::I64: - case ::HIR::CoreType::Isize: - TU_MATCH_DEF( PatternRule, (rule), (re), - ( - BUG(sp, "PatternRule for integer is not Value or ValueRange"); - ), - (Value, - auto succ_bb = builder.new_bb_unlinked(); - - auto test_lval = builder.lvalue_or_temp(sp, te, ::MIR::Constant(re.as_Int())); - auto cmp_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::EQ, mv$(test_lval) })); - builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_lval), succ_bb, fail_bb }) ); - builder.set_cur_block(succ_bb); - ), - (ValueRange, - TODO(sp, "Simple match over primitive - " << ty << " - ValueRange"); - ) - ) + case ::HIR::CoreType::Isize: { + int64_t start = H::get_pattern_value_int(sp, pat, pe.start); + int64_t end = H::get_pattern_value_int(sp, pat, pe.end ); + this->push_rule( PatternRule::make_ValueRange( {::MIR::Constant(start), ::MIR::Constant(end)} ) ); + } break; + case ::HIR::CoreType::Bool: + BUG(sp, "Can't range match on Bool"); break; - case ::HIR::CoreType::Char: - TU_MATCH_DEF( PatternRule, (rule), (re), - ( - BUG(sp, "PatternRule for char is not Value or ValueRange"); - ), - (Value, - auto succ_bb = builder.new_bb_unlinked(); - - auto test_lval = builder.lvalue_or_temp(sp, te, ::MIR::Constant(re.as_Uint())); - auto cmp_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::EQ, mv$(test_lval) })); - builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_lval), succ_bb, fail_bb }) ); - builder.set_cur_block(succ_bb); - ), - (ValueRange, - auto succ_bb = builder.new_bb_unlinked(); - auto test_bb_2 = builder.new_bb_unlinked(); - - // IF `match_val` < `first` : fail_bb - auto test_lt_lval = builder.lvalue_or_temp(sp, te, ::MIR::Constant(re.first.as_Uint())); - auto cmp_lt_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::LT, mv$(test_lt_lval) })); - builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_lt_lval), fail_bb, test_bb_2 }) ); - - builder.set_cur_block(test_bb_2); - - // IF `match_val` > `last` : fail_bb - auto test_gt_lval = builder.lvalue_or_temp(sp, te, ::MIR::Constant(re.last.as_Uint())); - auto cmp_gt_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::GT, mv$(test_gt_lval) })); - builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_gt_lval), fail_bb, succ_bb }) ); - - builder.set_cur_block(succ_bb); - ) - ) + case ::HIR::CoreType::Char: { + uint64_t start = H::get_pattern_value_int(sp, pat, pe.start); + uint64_t end = H::get_pattern_value_int(sp, pat, pe.end ); + this->push_rule( PatternRule::make_ValueRange( {::MIR::Constant(start), ::MIR::Constant(end)} ) ); + } break; + case ::HIR::CoreType::Str: + BUG(sp, "Hit match over `str` - must be `&str`"); break; + } + ), + (Value, + switch(e) + { case ::HIR::CoreType::F32: - case ::HIR::CoreType::F64: - TODO(sp, "Simple match over float - " << ty); + case ::HIR::CoreType::F64: { + // Yes, this is valid. + double val = H::get_pattern_value_float(sp, pat, pe.val); + this->push_rule( PatternRule::make_Value( ::MIR::Constant(val) ) ); + } break; + case ::HIR::CoreType::U8: + case ::HIR::CoreType::U16: + case ::HIR::CoreType::U32: + case ::HIR::CoreType::U64: + case ::HIR::CoreType::Usize: { + uint64_t val = H::get_pattern_value_int(sp, pat, pe.val); + this->push_rule( PatternRule::make_Value( ::MIR::Constant(val) ) ); + } break; + case ::HIR::CoreType::I8: + case ::HIR::CoreType::I16: + case ::HIR::CoreType::I32: + case ::HIR::CoreType::I64: + case ::HIR::CoreType::Isize: { + int64_t val = H::get_pattern_value_int(sp, pat, pe.val); + this->push_rule( PatternRule::make_Value( ::MIR::Constant(val) ) ); + } break; + case ::HIR::CoreType::Bool: + // TODO: Support values from `const` too + this->push_rule( PatternRule::make_Bool( pe.val.as_Integer().value != 0 ) ); break; + case ::HIR::CoreType::Char: { + // Char is just another name for 'u32'... but with a restricted range + uint64_t val = H::get_pattern_value_int(sp, pat, pe.val); + this->push_rule( PatternRule::make_Value( ::MIR::Constant(val) ) ); + } break; case ::HIR::CoreType::Str: - BUG(sp, "Match on str shouldn't hit this code"); + BUG(sp, "Hit match over `str` - must be `&str`"); break; } - } - return 1; + ) + ) + ), + (Tuple, + m_field_path.push_back(0); + TU_MATCH_DEF(::HIR::Pattern::Data, (pat.m_data), (pe), + ( BUG(sp, "Matching tuple with invalid pattern - " << pat); ), + (Any, + for(const auto& sty : e) { + this->append_from(sp, pat, sty); + m_field_path.back() ++; + } + ), + (Tuple, + assert(e.size() == pe.sub_patterns.size()); + for(unsigned int i = 0; i < e.size(); i ++) { + this->append_from(sp, pe.sub_patterns[i], e[i]); + m_field_path.back() ++; + } + ) + ) + m_field_path.pop_back(); ), (Path, - TU_MATCHA( (te.binding), (pbe), + // This is either a struct destructure or an enum + TU_MATCHA( (e.binding), (pbe), (Unbound, - BUG(sp, "Encounterd unbound path - " << te.path); + BUG(sp, "Encounterd unbound path - " << e.path); ), (Opaque, - if( !rule.is_Any() ) { - BUG(sp, "Attempting to match over opaque type - " << ty); - } - return 1; + TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), + ( BUG(sp, "Matching opaque type with invalid pattern - " << pat); ), + (Any, + this->push_rule( PatternRule::make_Any({}) ); + ) + ) ), (Struct, - auto monomorph = [&](const auto& ty) { return monomorphise_type(sp, pbe->m_params, te.path.m_data.as_Generic().m_params, ty); }; + auto monomorph = [&](const auto& ty) { + auto rv = monomorphise_type(sp, pbe->m_params, e.path.m_data.as_Generic().m_params, ty); + this->m_resolve.expand_associated_types(sp, rv); + return rv; + }; const auto& str_data = pbe->m_data; TU_MATCHA( (str_data), (sd), (Unit, - if( !rule.is_Any() ) { - BUG(sp, "Attempting to match over unit type - " << ty); - } - return 1; + TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), + ( BUG(sp, "Match not allowed, " << ty << " with " << pat); ), + (Any, + // Nothing. + //this->push_rule( PatternRule::make_Any({}) ); + ), + (Value, + //TODO(sp, "Match over struct - Unit + Value"); + ) + ) ), (Tuple, - if( !rule.is_Any() ) { - TODO(sp, "Match over tuple struct"); - } - return 1; + m_field_path.push_back(0); + TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), + ( BUG(sp, "Match not allowed, " << ty << " with " << pat); ), + (Any, + // - Recurse into type and use the same pattern again + for(const auto& fld : sd) + { + ::HIR::TypeRef tmp; + const auto& sty_mono = (monomorphise_type_needed(fld.ent) ? tmp = monomorph(fld.ent) : fld.ent); + this->append_from(sp, pat, sty_mono); + m_field_path.back() ++; + } + ), + (StructTuple, + TODO(sp, "Match over struct - TypeRef::Tuple + Pattern::StructTuple"); + ) + ) + m_field_path.pop_back(); ), (Named, - if( !rule.is_Any() ) { - unsigned int total = 0; - unsigned int i = 0; - for( const auto& fld : sd ) { - ::HIR::TypeRef ent_ty_tmp; - const auto& ent_ty = (monomorphise_type_needed(fld.second.ent) ? ent_ty_tmp = monomorph(fld.second.ent) : fld.second.ent); - unsigned int cnt = MIR_LowerHIR_Match_Simple__GeneratePattern( - builder, sp, - rules, num_rules, ent_ty, - ::MIR::LValue::make_Field({ box$(match_val.clone()), i }), - fail_bb - ); - total += cnt; - rules += cnt; - num_rules -= cnt; - i += 1; + TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), + ( BUG(sp, "Match not allowed, " << ty << " with " << pat); ), + (Any, + m_field_path.push_back(0); + for(const auto& fld : sd) + { + ::HIR::TypeRef tmp; + const auto& sty_mono = (monomorphise_type_needed(fld.second.ent) ? tmp = monomorph(fld.second.ent) : fld.second.ent); + this->append_from(sp, pat, sty_mono); + m_field_path.back() ++; } - return total; - } - else { - return 1; - } + m_field_path.pop_back(); + ), + (Struct, + m_field_path.push_back(0); + // NOTE: Sort field patterns to ensure that patterns are in order between arms + for(const auto& fld : sd) + { + ::HIR::TypeRef tmp; + const auto& sty_mono = (monomorphise_type_needed(fld.second.ent) ? tmp = monomorph(fld.second.ent) : fld.second.ent); + + auto it = ::std::find_if( pe.sub_patterns.begin(), pe.sub_patterns.end(), [&](const auto& x){ return x.first == fld.first; } ); + if( it == pe.sub_patterns.end() ) + { + ::HIR::Pattern any_pat {}; + this->append_from(sp, any_pat, sty_mono); + } + else + { + this->append_from(sp, it->second, sty_mono); + } + m_field_path.back() ++; + } + m_field_path.pop_back(); + ) + ) ) ) ), (Enum, - auto monomorph = [&](const auto& ty) { return monomorphise_type(sp, pbe->m_params, te.path.m_data.as_Generic().m_params, ty); }; - if( !rule.is_Any() ) { - ASSERT_BUG(sp, rule.is_Variant(), "Rule for enum isn't Any or Variant"); - const auto& re = rule.as_Variant(); - unsigned int var_idx = re.idx; - - auto next_bb = builder.new_bb_unlinked(); - auto var_count = pbe->m_variants.size(); - - // Generate a switch with only one option different. - ::std::vector< ::MIR::BasicBlockId> arms(var_count, fail_bb); - arms[var_idx] = next_bb; - builder.end_block( ::MIR::Terminator::make_Switch({ match_val.clone(), mv$(arms) }) ); + auto monomorph = [&](const auto& ty) { + auto rv = monomorphise_type(sp, pbe->m_params, e.path.m_data.as_Generic().m_params, ty); + this->m_resolve.expand_associated_types(sp, rv); + return rv; + }; + TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), + ( BUG(sp, "Match not allowed, " << ty << " with " << pat); ), + (Any, + this->push_rule( PatternRule::make_Any({}) ); + ), + (EnumValue, + this->push_rule( PatternRule::make_Variant( {pe.binding_idx, {} } ) ); + ), + (EnumTuple, + const auto& var_def = pe.binding_ptr->m_variants.at(pe.binding_idx); - builder.set_cur_block(next_bb); - - const auto& var_data = pbe->m_variants.at(re.idx).second; - TU_MATCHA( (var_data), (ve), - (Unit, - // Nothing to recurse - ), - (Value, - // Nothing to recurse - ), - (Tuple, - auto lval_var = ::MIR::LValue::make_Downcast({ box$(match_val.clone()), var_idx }); - const auto* subrules = re.sub_rules.data(); - unsigned int subrule_count = re.sub_rules.size(); + const auto& fields_def = var_def.second.as_Tuple(); + PatternRulesetBuilder sub_builder { this->m_resolve }; + sub_builder.m_field_path = m_field_path; + sub_builder.m_field_path.push_back(0); + for( unsigned int i = 0; i < pe.sub_patterns.size(); i ++ ) + { + sub_builder.m_field_path.back() = i; + const auto& subpat = pe.sub_patterns[i]; + const auto& ty_tpl = fields_def[i].ent; - for(unsigned int i = 0; i < ve.size(); i ++) - { - if( subrule_count == 0 ) - break ; - - ::HIR::TypeRef ent_ty_tmp; - const auto& ent_ty = (monomorphise_type_needed(ve[i].ent) ? ent_ty_tmp = monomorph(ve[i].ent) : ve[i].ent); - unsigned int cnt = MIR_LowerHIR_Match_Simple__GeneratePattern( - builder, sp, - subrules, subrule_count, ent_ty, - ::MIR::LValue::make_Field({ box$(lval_var.clone()), i }), - fail_bb - ); - subrules += cnt; - subrule_count -= cnt; - } - ), - (Struct, - auto lval_var = ::MIR::LValue::make_Downcast({ box$(match_val.clone()), var_idx }); - const auto* subrules = re.sub_rules.data(); - unsigned int subrule_count = re.sub_rules.size(); + ::HIR::TypeRef tmp; + const auto& subty = (monomorphise_type_needed(ty_tpl) ? tmp = monomorph(ty_tpl) : ty_tpl); - for(unsigned int i = 0; i < ve.size(); i ++) - { - if( subrule_count == 0 ) - break ; - - const auto& tpl_ty = ve[i].second.ent; - ::HIR::TypeRef ent_ty_tmp; - const auto& ent_ty = (monomorphise_type_needed(tpl_ty) ? ent_ty_tmp = monomorph(tpl_ty) : tpl_ty); - unsigned int cnt = MIR_LowerHIR_Match_Simple__GeneratePattern( - builder, sp, - subrules, subrule_count, ent_ty, - ::MIR::LValue::make_Field({ box$(lval_var.clone()), i }), - fail_bb - ); - subrules += cnt; - subrule_count -= cnt; + sub_builder.append_from( sp, subpat, subty ); + } + this->push_rule( PatternRule::make_Variant({ pe.binding_idx, mv$(sub_builder.m_rules) }) ); + ), + (EnumStruct, + const auto& var_def = pe.binding_ptr->m_variants.at(pe.binding_idx); + const auto& fields_def = var_def.second.as_Struct(); + // 1. Create a vector of pattern indexes for each field in the variant. + ::std::vector tmp; + tmp.resize( fields_def.size(), ~0u ); + for( unsigned int i = 0; i < pe.sub_patterns.size(); i ++ ) + { + const auto& fld_pat = pe.sub_patterns[i]; + unsigned idx = ::std::find_if( fields_def.begin(), fields_def.end(), [&](const auto& x){ return x.first == fld_pat.first; } ) - fields_def.begin(); + assert(idx < tmp.size()); + assert(tmp[idx] == ~0u); + tmp[idx] = i; + } + // 2. Iterate this list and recurse on the patterns + PatternRulesetBuilder sub_builder { this->m_resolve }; + sub_builder.m_field_path = m_field_path; + sub_builder.m_field_path.push_back(0); + for( unsigned int i = 0; i < tmp.size(); i ++ ) + { + sub_builder.m_field_path.back() = i; + + auto subty = monomorph(fields_def[i].second.ent); + if( tmp[i] == ~0u ) { + sub_builder.append_from( sp, ::HIR::Pattern(), subty ); } - ) + else { + const auto& subpat = pe.sub_patterns[ tmp[i] ].second; + sub_builder.append_from( sp, subpat, subty ); + } + } + this->push_rule( PatternRule::make_Variant({ pe.binding_idx, mv$(sub_builder.m_rules) }) ); ) - // NOTE: All enum variant patterns take one slot - return 1; - } - else { - return 1; - } + ) ) ) ), (Generic, - // Nothing needed - if( !rule.is_Any() ) { - BUG(sp, "Attempting to match a generic"); - } - return 1; + // Generics don't destructure, so the only valid pattern is `_` + TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), + ( BUG(sp, "Match not allowed, " << ty << " with " << pat); ), + (Any, + this->push_rule( PatternRule::make_Any({}) ); + ) + ) ), (TraitObject, - if( !rule.is_Any() ) { - BUG(sp, "Attempting to match a trait object"); + if( pat.m_data.is_Any() ) { + } + else { + ERROR(sp, E0000, "Attempting to match over a trait object"); } - return 1; ), (Array, - if( !rule.is_Any() ) { - unsigned int total = 0; - for( unsigned int i = 0; i < te.size_val; i ++ ) { - unsigned int cnt = MIR_LowerHIR_Match_Simple__GeneratePattern( - builder, sp, - rules, num_rules, *te.inner, - ::MIR::LValue::make_Field({ box$(match_val.clone()), i }), - fail_bb - ); - total += cnt; - rules += cnt; - num_rules -= cnt; - if( num_rules == 0 ) - return total; + // Sequential match just like tuples. + m_field_path.push_back(0); + TU_MATCH_DEF(::HIR::Pattern::Data, (pat.m_data), (pe), + ( BUG(sp, "Matching array with invalid pattern - " << pat); ), + (Any, + for(unsigned int i = 0; i < e.size_val; i ++) { + this->append_from(sp, pat, *e.inner); + m_field_path.back() ++; } - return total; - } - return 1; + ), + (Slice, + assert(e.size_val == pe.sub_patterns.size()); + for(unsigned int i = 0; i < e.size_val; i ++) { + this->append_from(sp, pe.sub_patterns[i], *e.inner); + m_field_path.back() ++; + } + ), + (SplitSlice, + TODO(sp, "Match over array with SplitSlice pattern - " << pat); + ) + ) + m_field_path.pop_back(); ), (Slice, - if( !rule.is_Any() ) { - TODO(sp, "Match over Slice - " << rule); - } - return 1; - ), - (Tuple, - if( !rule.is_Any() ) { - unsigned int total = 0; - for( unsigned int i = 0; i < te.size(); i ++ ) { - unsigned int cnt = MIR_LowerHIR_Match_Simple__GeneratePattern( - builder, sp, - rules, num_rules, te[i], - ::MIR::LValue::make_Field({ box$(match_val.clone()), i }), - fail_bb - ); - total += cnt; - rules += cnt; - num_rules -= cnt; - if( num_rules == 0 ) - return total; + TU_MATCH_DEF(::HIR::Pattern::Data, (pat.m_data), (pe), + ( + BUG(sp, "Matching over [T] with invalid pattern - " << pat); + ), + (Any, + // Value, don't add anything + ), + (Slice, + // Sub-patterns + PatternRulesetBuilder sub_builder { this->m_resolve }; + sub_builder.m_field_path = m_field_path; + sub_builder.m_field_path.push_back(0); + for(const auto& subpat : pe.sub_patterns) + { + sub_builder.append_from( sp, subpat, *e.inner ); + sub_builder.m_field_path.back() ++; } - return total; - } - return 1; + + // Encodes length check and sub-pattern rules + this->push_rule( PatternRule::make_Slice({ static_cast(pe.sub_patterns.size()), mv$(sub_builder.m_rules) }) ); + ), + (SplitSlice, + // 1. Length minimum check + // 2. Sub-patterns (handling trailing) + TODO(sp, "Match [T] with SplitSlice - " << pat); + ) + ) ), (Borrow, - if( rule.is_Value() ) { - const auto& v = rule.as_Value(); - if( v.is_StaticString() || v.is_Bytes() ) - { - ::MIR::Constant cloned_val; - if( v.is_StaticString() ) { - ASSERT_BUG(sp, *te.inner == ::HIR::TypeRef(::HIR::CoreType::Str), "StaticString pattern on non &str"); - cloned_val = ::MIR::Constant( v.as_StaticString() ); - } - else { - ASSERT_BUG(sp, *te.inner == ::HIR::TypeRef::new_slice(::HIR::CoreType::U8), "Bytes pattern on non-&[u8]"); - cloned_val = ::MIR::Constant( v.as_Bytes() ); - } - - auto succ_bb = builder.new_bb_unlinked(); + TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), + ( BUG(sp, "Matching borrow invalid pattern - " << pat); ), + (Any, + m_field_path.push_back( FIELD_DEREF ); + this->append_from( sp, pat, *e.inner ); + m_field_path.pop_back(); + ), + (Ref, + m_field_path.push_back( FIELD_DEREF ); + this->append_from( sp, *pe.sub, *e.inner ); + m_field_path.pop_back(); + ), + (Value, + // TODO: Check type? + if( pe.val.is_String() ) { + const auto& s = pe.val.as_String(); + this->push_rule( PatternRule::make_Value(s) ); + } + else if( pe.val.is_ByteString() ) { + const auto& s = pe.val.as_ByteString().v; + ::std::vector data; + data.reserve(s.size()); + for(auto c : s) + data.push_back(c); - auto test_lval = builder.lvalue_or_temp(sp, *te.inner, ::MIR::RValue(mv$(cloned_val))); - auto cmp_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::EQ, mv$(test_lval) })); - builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_lval), succ_bb, fail_bb }) ); - builder.set_cur_block(succ_bb); - return 1; + this->push_rule( PatternRule::make_Value( mv$(data) ) ); } - } - - if( !rule.is_Any() ) { - return MIR_LowerHIR_Match_Simple__GeneratePattern(builder, sp, rules, num_rules, *te.inner, match_val, fail_bb); - } - return 1; + // TODO: Handle named values + else { + BUG(sp, "Matching borrow invalid pattern - " << pat); + } + ) + ) ), (Pointer, - if( !rule.is_Any() ) { - BUG(sp, "Attempting to match a pointer"); + if( pat.m_data.is_Any() ) { + } + else { + ERROR(sp, E0000, "Attempting to match over a pointer"); } - return 1; ), (Function, - if( !rule.is_Any() ) { - BUG(sp, "Attempting to match a function pointer"); + if( pat.m_data.is_Any() ) { + } + else { + ERROR(sp, E0000, "Attempting to match over a functon pointer"); } - return 1; ), (Closure, - if( !rule.is_Any() ) { - BUG(sp, "Attempting to match a closure"); + if( pat.m_data.is_Any() ) { + } + else { + ERROR(sp, E0000, "Attempting to match over a closure"); } - return 1; ) ) - - throw ""; } // -------------------------------------------------------------------- -// Decision Tree +// Dumb and Simple // -------------------------------------------------------------------- +int MIR_LowerHIR_Match_Simple__GeneratePattern(MirBuilder& builder, const Span& sp, const PatternRule* rules, unsigned int num_rules, const ::HIR::TypeRef& ty, const ::MIR::LValue& match_val, ::MIR::BasicBlockId fail_bb); -// ## Create descision tree in-memory based off the ruleset -// > Tree contains an lvalue and a set of possibilities (PatternRule) connected to another tree or to a branch index -struct DecisionTreeNode +void MIR_LowerHIR_Match_Simple( MirBuilder& builder, MirConverter& conv, ::HIR::ExprNode_Match& node, ::MIR::LValue match_val, t_arm_rules arm_rules, ::std::vector arms_code, ::MIR::BasicBlockId first_cmp_block ) { - TAGGED_UNION( Branch, Unset, - (Unset, struct{}), - (Subtree, ::std::unique_ptr), - (Terminal, unsigned int) - ); + TRACE_FUNCTION; - template - struct Range + // 1. Generate pattern matches + unsigned int rule_idx = 0; + builder.set_cur_block( first_cmp_block ); + for( unsigned int arm_idx = 0; arm_idx < node.m_arms.size(); arm_idx ++ ) { - T start; - T end; - - // `x` starts after this range ends - bool operator<(const Range& x) const { - return (end < x.start); - } - // `x` falls above the end of this range - bool operator<(const T& x) const { - return (end < x); - } - - // `x` ends before this starts, or overlaps - bool operator>=(const Range& x) const { - return start > x.end || ovelaps(x); - } - // `x` is before or within this range - bool operator>=(const T& x) const { - return start > x || contains(x); - } + const auto& arm = node.m_arms[arm_idx]; + auto& arm_code = arms_code[arm_idx]; - bool operator>(const Range& x) const { - return (start > x.end); - } - bool operator>(const T& x) const { - return (start > x); - } + auto next_arm_bb = builder.new_bb_unlinked(); - bool contains(const T& x) const { - return (start <= x && x <= end); - } - bool overlaps(const Range& x) const { - return (x.start <= start && start <= x.end) || (x.start <= end && end <= x.end); - } - }; - - TAGGED_UNION( Values, Unset, - (Unset, struct {}), - (Bool, struct { Branch false_branch, true_branch; }), - (Variant, ::std::vector< ::std::pair >), - (Unsigned, ::std::vector< ::std::pair< Range, Branch> >), - (Signed, ::std::vector< ::std::pair< Range, Branch> >), - (Float, ::std::vector< ::std::pair< Range, Branch> >), - (String, ::std::vector< ::std::pair< ::std::string, Branch> >) - ); - - // TODO: Arm specialisation - bool is_specialisation; - PatternRule::field_path_t m_field_path; - Values m_branches; - Branch m_default; - - DecisionTreeNode( PatternRule::field_path_t field_path ): - is_specialisation(false)/*, - m_field_path( mv$(field_path) ) // */ - {} - - static Branch clone(const Branch& b); - static Values clone(const Values& x); - DecisionTreeNode clone() const; - - void populate_tree_from_rule(const Span& sp, unsigned int arm_index, const PatternRule* first_rule, unsigned int rule_count) { - populate_tree_from_rule(sp, first_rule, rule_count, [sp,arm_index](auto& branch){ - TU_MATCHA( (branch), (e), - (Unset, - // Good - ), - (Subtree, - if( e->m_branches.is_Unset() && e->m_default.is_Unset() ) { - // Good. - } - else { - BUG(sp, "Duplicate terminal - branch="< and_then); - - /// Simplifies the tree by eliminating nodes with just a default - void simplify(); - /// Propagate the m_default arm's contents to value arms, and vice-versa - void propagate_default(); - /// HELPER: Unfies the rules from the provided branch with this node - void unify_from(const Branch& b); - - ::MIR::LValue get_field(const ::MIR::LValue& base, unsigned int base_depth) const { - ::MIR::LValue cur = base.clone(); - for(unsigned int i = base_depth; i < m_field_path.size(); i ++ ) { - const auto idx = m_field_path[i]; - if( idx == FIELD_DEREF ) { - cur = ::MIR::LValue::make_Deref({ box$(cur) }); + for( unsigned int i = 0; i < arm.m_patterns.size(); i ++ ) + { + const auto& pat_rule = arm_rules[rule_idx]; + bool is_last_pat = (i+1 == arm.m_patterns.size()); + auto next_pattern_bb = (!is_last_pat ? builder.new_bb_unlinked() : next_arm_bb); + + // 1. Check + // - If the ruleset is empty, this is a _ arm over a value + if( pat_rule.m_rules.size() > 0 ) + { + MIR_LowerHIR_Match_Simple__GeneratePattern(builder, arm.m_code->span(), pat_rule.m_rules.data(), pat_rule.m_rules.size(), node.m_value->m_res_type, match_val, next_pattern_bb); } - else { - cur = ::MIR::LValue::make_Field({ box$(cur), idx }); + builder.end_block( ::MIR::Terminator::make_Goto(arm_code.destructures[i]) ); + builder.set_cur_block( arm_code.destructures[i] ); + + // - Go to code/condition check + if( arm_code.has_condition ) + { + builder.end_block( ::MIR::Terminator::make_Goto(arm_code.cond_start) ); + } + else + { + builder.end_block( ::MIR::Terminator::make_Goto(arm_code.code) ); + } + + if( !is_last_pat ) + { + builder.set_cur_block( next_pattern_bb ); } + + rule_idx ++; } - return cur; + if( arm_code.has_condition ) + { + builder.set_cur_block( arm_code.cond_end ); + builder.end_block( ::MIR::Terminator::make_If({ mv$(arm_code.cond_lval), arm_code.code, next_arm_bb }) ); + } + builder.set_cur_block( next_arm_bb ); } - - friend ::std::ostream& operator<<(::std::ostream& os, const Branch& x); - friend ::std::ostream& operator<<(::std::ostream& os, const DecisionTreeNode& x); -}; + // - Kill the final pattern block (which is dead code) + builder.end_block( ::MIR::Terminator::make_Diverge({}) ); +} -struct DecisionTreeGen +int MIR_LowerHIR_Match_Simple__GeneratePattern(MirBuilder& builder, const Span& sp, const PatternRule* rules, unsigned int num_rules, const ::HIR::TypeRef& ty, const ::MIR::LValue& match_val, ::MIR::BasicBlockId fail_bb) { - MirBuilder& m_builder; - const ::std::vector< ::MIR::BasicBlockId>& m_rule_blocks; - - DecisionTreeGen(MirBuilder& builder, const ::std::vector< ::MIR::BasicBlockId >& rule_blocks): - m_builder( builder ), - m_rule_blocks( rule_blocks ) - {} - - ::MIR::BasicBlockId get_block_for_rule(unsigned int rule_index) { - return m_rule_blocks.at( rule_index ); - } - - void get_ty_and_val( - const Span& sp, - const ::HIR::TypeRef& top_ty, const ::MIR::LValue& top_val, - const PatternRule::field_path_t& field_path, unsigned int field_path_ofs, - /*Out ->*/ ::HIR::TypeRef& out_ty, ::MIR::LValue& out_val - ); - - void generate_tree_code(const Span& sp, const DecisionTreeNode& node, const ::HIR::TypeRef& ty, const ::MIR::LValue& val) { - generate_tree_code(sp, node, ty, 0, val, [&](const auto& n){ - DEBUG("node = " << n); - // - Recurse on this method - this->generate_tree_code(sp, n, ty, val); - }); - } - void generate_tree_code( - const Span& sp, - const DecisionTreeNode& node, - const ::HIR::TypeRef& ty, unsigned int path_ofs, const ::MIR::LValue& base_val, - ::std::function and_then - ); - - void generate_branch(const DecisionTreeNode::Branch& branch, ::std::function cb); - - void generate_branches_Signed( - const Span& sp, - const DecisionTreeNode::Branch& default_branch, - const DecisionTreeNode::Values::Data_Signed& branches, - const ::HIR::TypeRef& ty, ::MIR::LValue val, - ::std::function and_then - ); - void generate_branches_Unsigned( - const Span& sp, - const DecisionTreeNode::Branch& default_branch, - const DecisionTreeNode::Values::Data_Unsigned& branches, - const ::HIR::TypeRef& ty, ::MIR::LValue val, - ::std::function and_then - ); - void generate_branches_Float( - const Span& sp, - const DecisionTreeNode::Branch& default_branch, - const DecisionTreeNode::Values::Data_Float& branches, - const ::HIR::TypeRef& ty, ::MIR::LValue val, - ::std::function and_then - ); - void generate_branches_Char( - const Span& sp, - const DecisionTreeNode::Branch& default_branch, - const DecisionTreeNode::Values::Data_Unsigned& branches, - const ::HIR::TypeRef& ty, ::MIR::LValue val, - ::std::function and_then - ); - void generate_branches_Bool( - const Span& sp, - const DecisionTreeNode::Branch& default_branch, - const DecisionTreeNode::Values::Data_Bool& branches, - const ::HIR::TypeRef& ty, ::MIR::LValue val, - ::std::function and_then - ); - void generate_branches_Borrow_str( - const Span& sp, - const DecisionTreeNode::Branch& default_branch, - const DecisionTreeNode::Values::Data_String& branches, - const ::HIR::TypeRef& ty, ::MIR::LValue val, - ::std::function and_then - ); - - void generate_branches_Enum( - const Span& sp, - const DecisionTreeNode::Branch& default_branch, - const DecisionTreeNode::Values::Data_Variant& branches, - const PatternRule::field_path_t& field_path, // used to know when to stop handling sub-nodes - const ::HIR::TypeRef& ty, ::MIR::LValue val, - ::std::function and_then - ); - void generate_tree_code__enum( - const Span& sp, - const DecisionTreeNode& node, const ::HIR::TypeRef& fake_ty, const ::MIR::LValue& val, - const PatternRule::field_path_t& path_prefix, - ::std::function and_then - ); -}; - -void MIR_LowerHIR_Match_DecisionTree( MirBuilder& builder, MirConverter& conv, ::HIR::ExprNode_Match& node, ::MIR::LValue match_val, t_arm_rules arm_rules, ::std::vector arms_code, ::MIR::BasicBlockId first_cmp_block ) -{ - TRACE_FUNCTION; - - // XXX XXX XXX: The current codegen (below) will generate incorrect code if ordering matters. - // ``` - // match ("foo", "bar") - // { - // (_, "bar") => {}, // Expected - // ("foo", _) => {}, // Actual - // _ => {}, - // } - // ``` - - // TODO: Sort the columns in `arm_rules` to ensure that the most specific rule is parsed first. - // - Ordering within a pattern doesn't matter, only the order of arms matters. - // - This sort could be designed such that the above case would match correctly? - - DEBUG("- Generating rule bindings"); - ::std::vector< ::MIR::BasicBlockId> rule_blocks; - for(const auto& rule : arm_rules) - { - const auto& arm_code = arms_code[rule.arm_idx]; - ASSERT_BUG(node.span(), !arm_code.has_condition, "Decision tree doesn't (yet) support conditionals"); - - assert( rule.pat_idx < arm_code.destructures.size() ); - // Set the target for when a rule succeeds to the destructuring code for this rule - rule_blocks.push_back( arm_code.destructures[rule.pat_idx] ); - // - Tie the end of that block to the code block for this arm - builder.set_cur_block( rule_blocks.back() ); - builder.end_block( ::MIR::Terminator::make_Goto(arm_code.code) ); - } - - - // - Build tree by running each arm's pattern across it - DEBUG("- Building decision tree"); - DecisionTreeNode root_node({}); - for( const auto& arm_rule : arm_rules ) - { - auto arm_idx = arm_rule.arm_idx; - DEBUG("(" << arm_idx << ", " << arm_rule.pat_idx << "): " << arm_rule.m_rules); - root_node.populate_tree_from_rule( node.m_arms[arm_idx].m_code->span(), arm_idx, arm_rule.m_rules.data(), arm_rule.m_rules.size() ); - } - DEBUG("root_node = " << root_node); - root_node.simplify(); - root_node.propagate_default(); - DEBUG("root_node = " << root_node); - - // - Convert the above decision tree into MIR - DEBUG("- Emitting decision tree"); - DecisionTreeGen gen { builder, rule_blocks }; - builder.set_cur_block( first_cmp_block ); - gen.generate_tree_code( node.span(), root_node, node.m_value->m_res_type, mv$(match_val) ); - ASSERT_BUG(node.span(), !builder.block_active(), "Decision tree didn't terminate the final block"); -} - -::std::ostream& operator<<(::std::ostream& os, const PatternRule& x) -{ - os <<"{"; - for(const auto idx : x.field_path) - os << "." << static_cast(idx); - os << "}="; - TU_MATCHA( (x), (e), - (Any, - os << "_"; - ), - // Enum variant - (Variant, - os << e.idx << " [" << e.sub_rules << "]"; - ), - // Enum variant - (Slice, - os << "len=" << e.len << " [" << e.sub_rules << "]"; - ), - // Boolean (different to Constant because of how restricted it is) - (Bool, - os << (e ? "true" : "false"); - ), - // General value - (Value, - os << e; - ), - (ValueRange, - os << e.first << " ... " << e.last; - ) - ) - return os; -} - -::Ordering PatternRuleset::rule_is_before(const PatternRule& l, const PatternRule& r) -{ - if( l.tag() != r.tag() ) { - // Any comes last, don't care about rest - if( l.tag() < r.tag() ) - return ::OrdGreater; - else - return ::OrdLess; - } - - TU_MATCHA( (l,r), (le,re), - (Any, - return ::OrdEqual; - ), - (Variant, - if( le.idx != re.idx ) - return ::ord(le.idx, re.idx); - assert( le.sub_rules.size() == re.sub_rules.size() ); - for(unsigned int i = 0; i < le.sub_rules.size(); i ++) - { - auto cmp = rule_is_before(le.sub_rules[i], re.sub_rules[i]); - if( cmp != ::OrdEqual ) - return cmp; - } - return ::OrdEqual; - ), - (Slice, - if( le.len != re.len ) - return ::ord(le.len, re.len); - // Wait? Why would the rule count be the same? - assert( le.sub_rules.size() == re.sub_rules.size() ); - for(unsigned int i = 0; i < le.sub_rules.size(); i ++) - { - auto cmp = rule_is_before(le.sub_rules[i], re.sub_rules[i]); - if( cmp != ::OrdEqual ) - return cmp; - } - return ::OrdEqual; - ), - (Bool, - return ::ord( le, re ); + TRACE_FUNCTION_F("ty = " << ty); + assert( num_rules > 0 ); + const auto& rule = *rules; + TU_MATCHA( (ty.m_data), (te), + (Infer, + BUG(sp, "Hit _ in type - " << ty); ), - (Value, - TODO(Span(), "Order PatternRule::Value"); + (Diverge, + BUG(sp, "Matching over !"); ), - (ValueRange, - TODO(Span(), "Order PatternRule::ValueRange"); - ) - ) - throw ""; -} - -bool PatternRuleset::is_before(const PatternRuleset& other) const -{ - assert( m_rules.size() == other.m_rules.size() ); - for(unsigned int i = 0; i < m_rules.size(); i ++) - { - const auto& l = m_rules[i]; - const auto& r = other.m_rules[i]; - auto cmp = rule_is_before(l, r); - if( cmp != ::OrdEqual ) - return cmp == ::OrdLess; - } - return false; -} - - -void PatternRulesetBuilder::push_rule(PatternRule r) -{ - m_rules.push_back( mv$(r) ); - m_rules.back().field_path = m_field_path; -} - -void PatternRulesetBuilder::append_from(const Span& sp, const ::HIR::Pattern& pat, const ::HIR::TypeRef& ty) -{ - TRACE_FUNCTION_F("pat="<m_value_res.as_Integer(); - ) - ) - throw ""; - } - static double get_pattern_value_float(const Span& sp, const ::HIR::Pattern& pat, const ::HIR::Pattern::Value& val) { - TU_MATCH_DEF( ::HIR::Pattern::Value, (val), (e), - ( - BUG(sp, "Invalid Value type in " << pat); - ), - (Float, - return e.value; - ), - (Named, - assert(e.binding); - return e.binding->m_value_res.as_Float(); - ) - ) - throw ""; - } - }; - - TU_MATCHA( (ty.m_data), (e), - (Infer, BUG(sp, "Ivar for in match type"); ), - (Diverge, BUG(sp, "Diverge in match type"); ), (Primitive, - TU_MATCH_DEF(::HIR::Pattern::Data, (pat.m_data), (pe), - ( BUG(sp, "Matching primitive with invalid pattern - " << pat); ), - (Any, - this->push_rule( PatternRule::make_Any({}) ); - ), - (Range, - switch(e) + if( !rule.is_Any() ) { + switch(te) { - case ::HIR::CoreType::F32: - case ::HIR::CoreType::F64: { - double start = H::get_pattern_value_float(sp, pat, pe.start); - double end = H::get_pattern_value_float(sp, pat, pe.end ); - this->push_rule( PatternRule::make_ValueRange( {::MIR::Constant(start), ::MIR::Constant(end)} ) ); + case ::HIR::CoreType::Bool: { + ASSERT_BUG(sp, rule.is_Bool(), "PatternRule for bool isn't _Bool"); + bool test_val = rule.as_Bool(); + + auto succ_bb = builder.new_bb_unlinked(); + + if( test_val ) { + builder.end_block( ::MIR::Terminator::make_If({ match_val.clone(), succ_bb, fail_bb }) ); + } + else { + builder.end_block( ::MIR::Terminator::make_If({ match_val.clone(), fail_bb, succ_bb }) ); + } + builder.set_cur_block(succ_bb); } break; case ::HIR::CoreType::U8: case ::HIR::CoreType::U16: case ::HIR::CoreType::U32: case ::HIR::CoreType::U64: - case ::HIR::CoreType::Usize: { - uint64_t start = H::get_pattern_value_int(sp, pat, pe.start); - uint64_t end = H::get_pattern_value_int(sp, pat, pe.end ); - this->push_rule( PatternRule::make_ValueRange( {::MIR::Constant(start), ::MIR::Constant(end)} ) ); - } break; - case ::HIR::CoreType::I8: - case ::HIR::CoreType::I16: - case ::HIR::CoreType::I32: - case ::HIR::CoreType::I64: - case ::HIR::CoreType::Isize: { - int64_t start = H::get_pattern_value_int(sp, pat, pe.start); - int64_t end = H::get_pattern_value_int(sp, pat, pe.end ); - this->push_rule( PatternRule::make_ValueRange( {::MIR::Constant(start), ::MIR::Constant(end)} ) ); - } break; - case ::HIR::CoreType::Bool: - BUG(sp, "Can't range match on Bool"); - break; - case ::HIR::CoreType::Char: { - uint64_t start = H::get_pattern_value_int(sp, pat, pe.start); - uint64_t end = H::get_pattern_value_int(sp, pat, pe.end ); - this->push_rule( PatternRule::make_ValueRange( {::MIR::Constant(start), ::MIR::Constant(end)} ) ); - } break; - case ::HIR::CoreType::Str: - BUG(sp, "Hit match over `str` - must be `&str`"); + case ::HIR::CoreType::Usize: + TU_MATCH_DEF( PatternRule, (rule), (re), + ( + BUG(sp, "PatternRule for integer is not Value or ValueRange"); + ), + (Value, + auto succ_bb = builder.new_bb_unlinked(); + + auto test_lval = builder.lvalue_or_temp(sp, te, ::MIR::Constant(re.as_Uint())); + auto cmp_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::EQ, mv$(test_lval) })); + builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_lval), succ_bb, fail_bb }) ); + builder.set_cur_block(succ_bb); + ), + (ValueRange, + TODO(sp, "Simple match over primitive - " << ty << " - ValueRange"); + ) + ) break; - } - ), - (Value, - switch(e) - { - case ::HIR::CoreType::F32: - case ::HIR::CoreType::F64: { - // Yes, this is valid. - double val = H::get_pattern_value_float(sp, pat, pe.val); - this->push_rule( PatternRule::make_Value( ::MIR::Constant(val) ) ); - } break; - case ::HIR::CoreType::U8: - case ::HIR::CoreType::U16: - case ::HIR::CoreType::U32: - case ::HIR::CoreType::U64: - case ::HIR::CoreType::Usize: { - uint64_t val = H::get_pattern_value_int(sp, pat, pe.val); - this->push_rule( PatternRule::make_Value( ::MIR::Constant(val) ) ); - } break; case ::HIR::CoreType::I8: case ::HIR::CoreType::I16: case ::HIR::CoreType::I32: case ::HIR::CoreType::I64: - case ::HIR::CoreType::Isize: { - int64_t val = H::get_pattern_value_int(sp, pat, pe.val); - this->push_rule( PatternRule::make_Value( ::MIR::Constant(val) ) ); - } break; - case ::HIR::CoreType::Bool: - // TODO: Support values from `const` too - this->push_rule( PatternRule::make_Bool( pe.val.as_Integer().value != 0 ) ); + case ::HIR::CoreType::Isize: + TU_MATCH_DEF( PatternRule, (rule), (re), + ( + BUG(sp, "PatternRule for integer is not Value or ValueRange"); + ), + (Value, + auto succ_bb = builder.new_bb_unlinked(); + + auto test_lval = builder.lvalue_or_temp(sp, te, ::MIR::Constant(re.as_Int())); + auto cmp_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::EQ, mv$(test_lval) })); + builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_lval), succ_bb, fail_bb }) ); + builder.set_cur_block(succ_bb); + ), + (ValueRange, + TODO(sp, "Simple match over primitive - " << ty << " - ValueRange"); + ) + ) + break; + case ::HIR::CoreType::Char: + TU_MATCH_DEF( PatternRule, (rule), (re), + ( + BUG(sp, "PatternRule for char is not Value or ValueRange"); + ), + (Value, + auto succ_bb = builder.new_bb_unlinked(); + + auto test_lval = builder.lvalue_or_temp(sp, te, ::MIR::Constant(re.as_Uint())); + auto cmp_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::EQ, mv$(test_lval) })); + builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_lval), succ_bb, fail_bb }) ); + builder.set_cur_block(succ_bb); + ), + (ValueRange, + auto succ_bb = builder.new_bb_unlinked(); + auto test_bb_2 = builder.new_bb_unlinked(); + + // IF `match_val` < `first` : fail_bb + auto test_lt_lval = builder.lvalue_or_temp(sp, te, ::MIR::Constant(re.first.as_Uint())); + auto cmp_lt_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::LT, mv$(test_lt_lval) })); + builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_lt_lval), fail_bb, test_bb_2 }) ); + + builder.set_cur_block(test_bb_2); + + // IF `match_val` > `last` : fail_bb + auto test_gt_lval = builder.lvalue_or_temp(sp, te, ::MIR::Constant(re.last.as_Uint())); + auto cmp_gt_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::GT, mv$(test_gt_lval) })); + builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_gt_lval), fail_bb, succ_bb }) ); + + builder.set_cur_block(succ_bb); + ) + ) + break; + case ::HIR::CoreType::F32: + case ::HIR::CoreType::F64: + TODO(sp, "Simple match over float - " << ty); break; - case ::HIR::CoreType::Char: { - // Char is just another name for 'u32'... but with a restricted range - uint64_t val = H::get_pattern_value_int(sp, pat, pe.val); - this->push_rule( PatternRule::make_Value( ::MIR::Constant(val) ) ); - } break; case ::HIR::CoreType::Str: - BUG(sp, "Hit match over `str` - must be `&str`"); + BUG(sp, "Match on str shouldn't hit this code"); break; } - ) - ) - ), - (Tuple, - m_field_path.push_back(0); - TU_MATCH_DEF(::HIR::Pattern::Data, (pat.m_data), (pe), - ( BUG(sp, "Matching tuple with invalid pattern - " << pat); ), - (Any, - for(const auto& sty : e) { - this->append_from(sp, pat, sty); - m_field_path.back() ++; - } - ), - (Tuple, - assert(e.size() == pe.sub_patterns.size()); - for(unsigned int i = 0; i < e.size(); i ++) { - this->append_from(sp, pe.sub_patterns[i], e[i]); - m_field_path.back() ++; - } - ) - ) - m_field_path.pop_back(); + } + return 1; ), (Path, - // This is either a struct destructure or an enum - TU_MATCHA( (e.binding), (pbe), + TU_MATCHA( (te.binding), (pbe), (Unbound, - BUG(sp, "Encounterd unbound path - " << e.path); + BUG(sp, "Encounterd unbound path - " << te.path); ), (Opaque, - TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), - ( BUG(sp, "Matching opaque type with invalid pattern - " << pat); ), - (Any, - this->push_rule( PatternRule::make_Any({}) ); - ) - ) + if( !rule.is_Any() ) { + BUG(sp, "Attempting to match over opaque type - " << ty); + } + return 1; ), (Struct, - auto monomorph = [&](const auto& ty) { - auto rv = monomorphise_type(sp, pbe->m_params, e.path.m_data.as_Generic().m_params, ty); - this->m_resolve.expand_associated_types(sp, rv); - return rv; - }; + auto monomorph = [&](const auto& ty) { return monomorphise_type(sp, pbe->m_params, te.path.m_data.as_Generic().m_params, ty); }; const auto& str_data = pbe->m_data; TU_MATCHA( (str_data), (sd), (Unit, - TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), - ( BUG(sp, "Match not allowed, " << ty << " with " << pat); ), - (Any, - // Nothing. - //this->push_rule( PatternRule::make_Any({}) ); - ), - (Value, - //TODO(sp, "Match over struct - Unit + Value"); - ) - ) + if( !rule.is_Any() ) { + BUG(sp, "Attempting to match over unit type - " << ty); + } + return 1; ), (Tuple, - m_field_path.push_back(0); - TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), - ( BUG(sp, "Match not allowed, " << ty << " with " << pat); ), - (Any, - // - Recurse into type and use the same pattern again - for(const auto& fld : sd) - { - ::HIR::TypeRef tmp; - const auto& sty_mono = (monomorphise_type_needed(fld.ent) ? tmp = monomorph(fld.ent) : fld.ent); - this->append_from(sp, pat, sty_mono); - m_field_path.back() ++; - } - ), - (StructTuple, - TODO(sp, "Match over struct - TypeRef::Tuple + Pattern::StructTuple"); - ) - ) - m_field_path.pop_back(); + if( !rule.is_Any() ) { + TODO(sp, "Match over tuple struct"); + } + return 1; ), (Named, - TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), - ( BUG(sp, "Match not allowed, " << ty << " with " << pat); ), - (Any, - m_field_path.push_back(0); - for(const auto& fld : sd) - { - ::HIR::TypeRef tmp; - const auto& sty_mono = (monomorphise_type_needed(fld.second.ent) ? tmp = monomorph(fld.second.ent) : fld.second.ent); - this->append_from(sp, pat, sty_mono); - m_field_path.back() ++; - } - m_field_path.pop_back(); - ), - (Struct, - m_field_path.push_back(0); - // NOTE: Sort field patterns to ensure that patterns are in order between arms - for(const auto& fld : sd) - { - ::HIR::TypeRef tmp; - const auto& sty_mono = (monomorphise_type_needed(fld.second.ent) ? tmp = monomorph(fld.second.ent) : fld.second.ent); - - auto it = ::std::find_if( pe.sub_patterns.begin(), pe.sub_patterns.end(), [&](const auto& x){ return x.first == fld.first; } ); - if( it == pe.sub_patterns.end() ) - { - ::HIR::Pattern any_pat {}; - this->append_from(sp, any_pat, sty_mono); - } - else - { - this->append_from(sp, it->second, sty_mono); - } - m_field_path.back() ++; + if( !rule.is_Any() ) { + unsigned int total = 0; + unsigned int i = 0; + for( const auto& fld : sd ) { + ::HIR::TypeRef ent_ty_tmp; + const auto& ent_ty = (monomorphise_type_needed(fld.second.ent) ? ent_ty_tmp = monomorph(fld.second.ent) : fld.second.ent); + unsigned int cnt = MIR_LowerHIR_Match_Simple__GeneratePattern( + builder, sp, + rules, num_rules, ent_ty, + ::MIR::LValue::make_Field({ box$(match_val.clone()), i }), + fail_bb + ); + total += cnt; + rules += cnt; + num_rules -= cnt; + i += 1; } - m_field_path.pop_back(); - ) - ) + return total; + } + else { + return 1; + } ) ) ), (Enum, - auto monomorph = [&](const auto& ty) { - auto rv = monomorphise_type(sp, pbe->m_params, e.path.m_data.as_Generic().m_params, ty); - this->m_resolve.expand_associated_types(sp, rv); - return rv; - }; - TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), - ( BUG(sp, "Match not allowed, " << ty << " with " << pat); ), - (Any, - this->push_rule( PatternRule::make_Any({}) ); - ), - (EnumValue, - this->push_rule( PatternRule::make_Variant( {pe.binding_idx, {} } ) ); - ), - (EnumTuple, - const auto& var_def = pe.binding_ptr->m_variants.at(pe.binding_idx); + auto monomorph = [&](const auto& ty) { return monomorphise_type(sp, pbe->m_params, te.path.m_data.as_Generic().m_params, ty); }; + if( !rule.is_Any() ) { + ASSERT_BUG(sp, rule.is_Variant(), "Rule for enum isn't Any or Variant"); + const auto& re = rule.as_Variant(); + unsigned int var_idx = re.idx; - const auto& fields_def = var_def.second.as_Tuple(); - PatternRulesetBuilder sub_builder { this->m_resolve }; - sub_builder.m_field_path = m_field_path; - sub_builder.m_field_path.push_back(0); - for( unsigned int i = 0; i < pe.sub_patterns.size(); i ++ ) - { - sub_builder.m_field_path.back() = i; - const auto& subpat = pe.sub_patterns[i]; - const auto& ty_tpl = fields_def[i].ent; - - ::HIR::TypeRef tmp; - const auto& subty = (monomorphise_type_needed(ty_tpl) ? tmp = monomorph(ty_tpl) : ty_tpl); - - sub_builder.append_from( sp, subpat, subty ); - } - this->push_rule( PatternRule::make_Variant({ pe.binding_idx, mv$(sub_builder.m_rules) }) ); - ), - (EnumStruct, - const auto& var_def = pe.binding_ptr->m_variants.at(pe.binding_idx); - const auto& fields_def = var_def.second.as_Struct(); - // 1. Create a vector of pattern indexes for each field in the variant. - ::std::vector tmp; - tmp.resize( fields_def.size(), ~0u ); - for( unsigned int i = 0; i < pe.sub_patterns.size(); i ++ ) - { - const auto& fld_pat = pe.sub_patterns[i]; - unsigned idx = ::std::find_if( fields_def.begin(), fields_def.end(), [&](const auto& x){ return x.first == fld_pat.first; } ) - fields_def.begin(); - assert(idx < tmp.size()); - assert(tmp[idx] == ~0u); - tmp[idx] = i; - } - // 2. Iterate this list and recurse on the patterns - PatternRulesetBuilder sub_builder { this->m_resolve }; - sub_builder.m_field_path = m_field_path; - sub_builder.m_field_path.push_back(0); - for( unsigned int i = 0; i < tmp.size(); i ++ ) - { - sub_builder.m_field_path.back() = i; + auto next_bb = builder.new_bb_unlinked(); + auto var_count = pbe->m_variants.size(); + + // Generate a switch with only one option different. + ::std::vector< ::MIR::BasicBlockId> arms(var_count, fail_bb); + arms[var_idx] = next_bb; + builder.end_block( ::MIR::Terminator::make_Switch({ match_val.clone(), mv$(arms) }) ); + + builder.set_cur_block(next_bb); + + const auto& var_data = pbe->m_variants.at(re.idx).second; + TU_MATCHA( (var_data), (ve), + (Unit, + // Nothing to recurse + ), + (Value, + // Nothing to recurse + ), + (Tuple, + auto lval_var = ::MIR::LValue::make_Downcast({ box$(match_val.clone()), var_idx }); + const auto* subrules = re.sub_rules.data(); + unsigned int subrule_count = re.sub_rules.size(); - auto subty = monomorph(fields_def[i].second.ent); - if( tmp[i] == ~0u ) { - sub_builder.append_from( sp, ::HIR::Pattern(), subty ); + for(unsigned int i = 0; i < ve.size(); i ++) + { + if( subrule_count == 0 ) + break ; + + ::HIR::TypeRef ent_ty_tmp; + const auto& ent_ty = (monomorphise_type_needed(ve[i].ent) ? ent_ty_tmp = monomorph(ve[i].ent) : ve[i].ent); + unsigned int cnt = MIR_LowerHIR_Match_Simple__GeneratePattern( + builder, sp, + subrules, subrule_count, ent_ty, + ::MIR::LValue::make_Field({ box$(lval_var.clone()), i }), + fail_bb + ); + subrules += cnt; + subrule_count -= cnt; } - else { - const auto& subpat = pe.sub_patterns[ tmp[i] ].second; - sub_builder.append_from( sp, subpat, subty ); + ), + (Struct, + auto lval_var = ::MIR::LValue::make_Downcast({ box$(match_val.clone()), var_idx }); + const auto* subrules = re.sub_rules.data(); + unsigned int subrule_count = re.sub_rules.size(); + + for(unsigned int i = 0; i < ve.size(); i ++) + { + if( subrule_count == 0 ) + break ; + + const auto& tpl_ty = ve[i].second.ent; + ::HIR::TypeRef ent_ty_tmp; + const auto& ent_ty = (monomorphise_type_needed(tpl_ty) ? ent_ty_tmp = monomorph(tpl_ty) : tpl_ty); + unsigned int cnt = MIR_LowerHIR_Match_Simple__GeneratePattern( + builder, sp, + subrules, subrule_count, ent_ty, + ::MIR::LValue::make_Field({ box$(lval_var.clone()), i }), + fail_bb + ); + subrules += cnt; + subrule_count -= cnt; } - } - this->push_rule( PatternRule::make_Variant({ pe.binding_idx, mv$(sub_builder.m_rules) }) ); + ) ) - ) + // NOTE: All enum variant patterns take one slot + return 1; + } + else { + return 1; + } ) ) ), (Generic, - // Generics don't destructure, so the only valid pattern is `_` - TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), - ( BUG(sp, "Match not allowed, " << ty << " with " << pat); ), - (Any, - this->push_rule( PatternRule::make_Any({}) ); - ) - ) + // Nothing needed + if( !rule.is_Any() ) { + BUG(sp, "Attempting to match a generic"); + } + return 1; ), (TraitObject, - if( pat.m_data.is_Any() ) { - } - else { - ERROR(sp, E0000, "Attempting to match over a trait object"); + if( !rule.is_Any() ) { + BUG(sp, "Attempting to match a trait object"); } + return 1; ), (Array, - // Sequential match just like tuples. - m_field_path.push_back(0); - TU_MATCH_DEF(::HIR::Pattern::Data, (pat.m_data), (pe), - ( BUG(sp, "Matching array with invalid pattern - " << pat); ), - (Any, - for(unsigned int i = 0; i < e.size_val; i ++) { - this->append_from(sp, pat, *e.inner); - m_field_path.back() ++; - } - ), - (Slice, - assert(e.size_val == pe.sub_patterns.size()); - for(unsigned int i = 0; i < e.size_val; i ++) { - this->append_from(sp, pe.sub_patterns[i], *e.inner); - m_field_path.back() ++; + if( !rule.is_Any() ) { + unsigned int total = 0; + for( unsigned int i = 0; i < te.size_val; i ++ ) { + unsigned int cnt = MIR_LowerHIR_Match_Simple__GeneratePattern( + builder, sp, + rules, num_rules, *te.inner, + ::MIR::LValue::make_Field({ box$(match_val.clone()), i }), + fail_bb + ); + total += cnt; + rules += cnt; + num_rules -= cnt; + if( num_rules == 0 ) + return total; } - ), - (SplitSlice, - TODO(sp, "Match over array with SplitSlice pattern - " << pat); - ) - ) - m_field_path.pop_back(); + return total; + } + return 1; ), (Slice, - TU_MATCH_DEF(::HIR::Pattern::Data, (pat.m_data), (pe), - ( - BUG(sp, "Matching over [T] with invalid pattern - " << pat); - ), - (Any, - // Value, don't add anything - ), - (Slice, - // Sub-patterns - PatternRulesetBuilder sub_builder { this->m_resolve }; - sub_builder.m_field_path = m_field_path; - sub_builder.m_field_path.push_back(0); - for(const auto& subpat : pe.sub_patterns) - { - sub_builder.append_from( sp, subpat, *e.inner ); - sub_builder.m_field_path.back() ++; + if( !rule.is_Any() ) { + TODO(sp, "Match over Slice - " << rule); + } + return 1; + ), + (Tuple, + if( !rule.is_Any() ) { + unsigned int total = 0; + for( unsigned int i = 0; i < te.size(); i ++ ) { + unsigned int cnt = MIR_LowerHIR_Match_Simple__GeneratePattern( + builder, sp, + rules, num_rules, te[i], + ::MIR::LValue::make_Field({ box$(match_val.clone()), i }), + fail_bb + ); + total += cnt; + rules += cnt; + num_rules -= cnt; + if( num_rules == 0 ) + return total; } - - // Encodes length check and sub-pattern rules - this->push_rule( PatternRule::make_Slice({ static_cast(pe.sub_patterns.size()), mv$(sub_builder.m_rules) }) ); - ), - (SplitSlice, - // 1. Length minimum check - // 2. Sub-patterns (handling trailing) - TODO(sp, "Match [T] with SplitSlice - " << pat); - ) - ) + return total; + } + return 1; ), (Borrow, - TU_MATCH_DEF( ::HIR::Pattern::Data, (pat.m_data), (pe), - ( BUG(sp, "Matching borrow invalid pattern - " << pat); ), - (Any, - m_field_path.push_back( FIELD_DEREF ); - this->append_from( sp, pat, *e.inner ); - m_field_path.pop_back(); - ), - (Ref, - m_field_path.push_back( FIELD_DEREF ); - this->append_from( sp, *pe.sub, *e.inner ); - m_field_path.pop_back(); - ), - (Value, - // TODO: Check type? - if( pe.val.is_String() ) { - const auto& s = pe.val.as_String(); - this->push_rule( PatternRule::make_Value(s) ); - } - else if( pe.val.is_ByteString() ) { - const auto& s = pe.val.as_ByteString().v; - ::std::vector data; - data.reserve(s.size()); - for(auto c : s) - data.push_back(c); + if( rule.is_Value() ) { + const auto& v = rule.as_Value(); + if( v.is_StaticString() || v.is_Bytes() ) + { + ::MIR::Constant cloned_val; + if( v.is_StaticString() ) { + ASSERT_BUG(sp, *te.inner == ::HIR::TypeRef(::HIR::CoreType::Str), "StaticString pattern on non &str"); + cloned_val = ::MIR::Constant( v.as_StaticString() ); + } + else { + ASSERT_BUG(sp, *te.inner == ::HIR::TypeRef::new_slice(::HIR::CoreType::U8), "Bytes pattern on non-&[u8]"); + cloned_val = ::MIR::Constant( v.as_Bytes() ); + } - this->push_rule( PatternRule::make_Value( mv$(data) ) ); - } - // TODO: Handle named values - else { - BUG(sp, "Matching borrow invalid pattern - " << pat); + auto succ_bb = builder.new_bb_unlinked(); + + auto test_lval = builder.lvalue_or_temp(sp, *te.inner, ::MIR::RValue(mv$(cloned_val))); + auto cmp_lval = builder.lvalue_or_temp(sp, ::HIR::CoreType::Bool, ::MIR::RValue::make_BinOp({ match_val.clone(), ::MIR::eBinOp::EQ, mv$(test_lval) })); + builder.end_block( ::MIR::Terminator::make_If({ mv$(cmp_lval), succ_bb, fail_bb }) ); + builder.set_cur_block(succ_bb); + return 1; } - ) - ) + } + + if( !rule.is_Any() ) { + return MIR_LowerHIR_Match_Simple__GeneratePattern(builder, sp, rules, num_rules, *te.inner, match_val, fail_bb); + } + return 1; ), (Pointer, - if( pat.m_data.is_Any() ) { + if( !rule.is_Any() ) { + BUG(sp, "Attempting to match a pointer"); + } + return 1; + ), + (Function, + if( !rule.is_Any() ) { + BUG(sp, "Attempting to match a function pointer"); + } + return 1; + ), + (Closure, + if( !rule.is_Any() ) { + BUG(sp, "Attempting to match a closure"); + } + return 1; + ) + ) + + throw ""; +} + +// -------------------------------------------------------------------- +// Decision Tree +// -------------------------------------------------------------------- + +// ## Create descision tree in-memory based off the ruleset +// > Tree contains an lvalue and a set of possibilities (PatternRule) connected to another tree or to a branch index +struct DecisionTreeNode +{ + TAGGED_UNION( Branch, Unset, + (Unset, struct{}), + (Subtree, ::std::unique_ptr), + (Terminal, unsigned int) + ); + + template + struct Range + { + T start; + T end; + + // `x` starts after this range ends + bool operator<(const Range& x) const { + return (end < x.start); + } + // `x` falls above the end of this range + bool operator<(const T& x) const { + return (end < x); + } + + // `x` ends before this starts, or overlaps + bool operator>=(const Range& x) const { + return start > x.end || ovelaps(x); } - else { - ERROR(sp, E0000, "Attempting to match over a pointer"); + // `x` is before or within this range + bool operator>=(const T& x) const { + return start > x || contains(x); } - ), - (Function, - if( pat.m_data.is_Any() ) { + + bool operator>(const Range& x) const { + return (start > x.end); } - else { - ERROR(sp, E0000, "Attempting to match over a functon pointer"); + bool operator>(const T& x) const { + return (start > x); } - ), - (Closure, - if( pat.m_data.is_Any() ) { + + bool contains(const T& x) const { + return (start <= x && x <= end); } - else { - ERROR(sp, E0000, "Attempting to match over a closure"); + bool overlaps(const Range& x) const { + return (x.start <= start && start <= x.end) || (x.start <= end && end <= x.end); } - ) - ) -} + }; + + TAGGED_UNION( Values, Unset, + (Unset, struct {}), + (Bool, struct { Branch false_branch, true_branch; }), + (Variant, ::std::vector< ::std::pair >), + (Unsigned, ::std::vector< ::std::pair< Range, Branch> >), + (Signed, ::std::vector< ::std::pair< Range, Branch> >), + (Float, ::std::vector< ::std::pair< Range, Branch> >), + (String, ::std::vector< ::std::pair< ::std::string, Branch> >) + ); + + // TODO: Arm specialisation + bool is_specialisation; + PatternRule::field_path_t m_field_path; + Values m_branches; + Branch m_default; + + DecisionTreeNode( PatternRule::field_path_t field_path ): + is_specialisation(false)/*, + m_field_path( mv$(field_path) ) // */ + {} + + static Branch clone(const Branch& b); + static Values clone(const Values& x); + DecisionTreeNode clone() const; + + void populate_tree_from_rule(const Span& sp, unsigned int arm_index, const PatternRule* first_rule, unsigned int rule_count) { + populate_tree_from_rule(sp, first_rule, rule_count, [sp,arm_index](auto& branch){ + TU_MATCHA( (branch), (e), + (Unset, + // Good + ), + (Subtree, + if( e->m_branches.is_Unset() && e->m_default.is_Unset() ) { + // Good. + } + else { + BUG(sp, "Duplicate terminal - branch="< and_then); + + /// Simplifies the tree by eliminating nodes with just a default + void simplify(); + /// Propagate the m_default arm's contents to value arms, and vice-versa + void propagate_default(); + /// HELPER: Unfies the rules from the provided branch with this node + void unify_from(const Branch& b); + + ::MIR::LValue get_field(const ::MIR::LValue& base, unsigned int base_depth) const { + ::MIR::LValue cur = base.clone(); + for(unsigned int i = base_depth; i < m_field_path.size(); i ++ ) { + const auto idx = m_field_path[i]; + if( idx == FIELD_DEREF ) { + cur = ::MIR::LValue::make_Deref({ box$(cur) }); + } + else { + cur = ::MIR::LValue::make_Field({ box$(cur), idx }); + } + } + return cur; + } + + friend ::std::ostream& operator<<(::std::ostream& os, const Branch& x); + friend ::std::ostream& operator<<(::std::ostream& os, const DecisionTreeNode& x); +}; + +struct DecisionTreeGen +{ + MirBuilder& m_builder; + const ::std::vector< ::MIR::BasicBlockId>& m_rule_blocks; + + DecisionTreeGen(MirBuilder& builder, const ::std::vector< ::MIR::BasicBlockId >& rule_blocks): + m_builder( builder ), + m_rule_blocks( rule_blocks ) + {} + + ::MIR::BasicBlockId get_block_for_rule(unsigned int rule_index) { + return m_rule_blocks.at( rule_index ); + } + + void get_ty_and_val( + const Span& sp, + const ::HIR::TypeRef& top_ty, const ::MIR::LValue& top_val, + const PatternRule::field_path_t& field_path, unsigned int field_path_ofs, + /*Out ->*/ ::HIR::TypeRef& out_ty, ::MIR::LValue& out_val + ); + + void generate_tree_code(const Span& sp, const DecisionTreeNode& node, const ::HIR::TypeRef& ty, const ::MIR::LValue& val) { + generate_tree_code(sp, node, ty, 0, val, [&](const auto& n){ + DEBUG("node = " << n); + // - Recurse on this method + this->generate_tree_code(sp, n, ty, val); + }); + } + void generate_tree_code( + const Span& sp, + const DecisionTreeNode& node, + const ::HIR::TypeRef& ty, unsigned int path_ofs, const ::MIR::LValue& base_val, + ::std::function and_then + ); + + void generate_branch(const DecisionTreeNode::Branch& branch, ::std::function cb); + + void generate_branches_Signed( + const Span& sp, + const DecisionTreeNode::Branch& default_branch, + const DecisionTreeNode::Values::Data_Signed& branches, + const ::HIR::TypeRef& ty, ::MIR::LValue val, + ::std::function and_then + ); + void generate_branches_Unsigned( + const Span& sp, + const DecisionTreeNode::Branch& default_branch, + const DecisionTreeNode::Values::Data_Unsigned& branches, + const ::HIR::TypeRef& ty, ::MIR::LValue val, + ::std::function and_then + ); + void generate_branches_Float( + const Span& sp, + const DecisionTreeNode::Branch& default_branch, + const DecisionTreeNode::Values::Data_Float& branches, + const ::HIR::TypeRef& ty, ::MIR::LValue val, + ::std::function and_then + ); + void generate_branches_Char( + const Span& sp, + const DecisionTreeNode::Branch& default_branch, + const DecisionTreeNode::Values::Data_Unsigned& branches, + const ::HIR::TypeRef& ty, ::MIR::LValue val, + ::std::function and_then + ); + void generate_branches_Bool( + const Span& sp, + const DecisionTreeNode::Branch& default_branch, + const DecisionTreeNode::Values::Data_Bool& branches, + const ::HIR::TypeRef& ty, ::MIR::LValue val, + ::std::function and_then + ); + void generate_branches_Borrow_str( + const Span& sp, + const DecisionTreeNode::Branch& default_branch, + const DecisionTreeNode::Values::Data_String& branches, + const ::HIR::TypeRef& ty, ::MIR::LValue val, + ::std::function and_then + ); + + void generate_branches_Enum( + const Span& sp, + const DecisionTreeNode::Branch& default_branch, + const DecisionTreeNode::Values::Data_Variant& branches, + const PatternRule::field_path_t& field_path, // used to know when to stop handling sub-nodes + const ::HIR::TypeRef& ty, ::MIR::LValue val, + ::std::function and_then + ); + void generate_tree_code__enum( + const Span& sp, + const DecisionTreeNode& node, const ::HIR::TypeRef& fake_ty, const ::MIR::LValue& val, + const PatternRule::field_path_t& path_prefix, + ::std::function and_then + ); +}; + +void MIR_LowerHIR_Match_DecisionTree( MirBuilder& builder, MirConverter& conv, ::HIR::ExprNode_Match& node, ::MIR::LValue match_val, t_arm_rules arm_rules, ::std::vector arms_code, ::MIR::BasicBlockId first_cmp_block ) +{ + TRACE_FUNCTION; + + // XXX XXX XXX: The current codegen (below) will generate incorrect code if ordering matters. + // ``` + // match ("foo", "bar") + // { + // (_, "bar") => {}, // Expected + // ("foo", _) => {}, // Actual + // _ => {}, + // } + // ``` + // TODO: Sort the columns in `arm_rules` to ensure that the most specific rule is parsed first. + // - Ordering within a pattern doesn't matter, only the order of arms matters. + // - This sort could be designed such that the above case would match correctly? + + DEBUG("- Generating rule bindings"); + ::std::vector< ::MIR::BasicBlockId> rule_blocks; + for(const auto& rule : arm_rules) + { + const auto& arm_code = arms_code[rule.arm_idx]; + ASSERT_BUG(node.span(), !arm_code.has_condition, "Decision tree doesn't (yet) support conditionals"); + + assert( rule.pat_idx < arm_code.destructures.size() ); + // Set the target for when a rule succeeds to the destructuring code for this rule + rule_blocks.push_back( arm_code.destructures[rule.pat_idx] ); + // - Tie the end of that block to the code block for this arm + builder.set_cur_block( rule_blocks.back() ); + builder.end_block( ::MIR::Terminator::make_Goto(arm_code.code) ); + } + + + // - Build tree by running each arm's pattern across it + DEBUG("- Building decision tree"); + DecisionTreeNode root_node({}); + for( const auto& arm_rule : arm_rules ) + { + auto arm_idx = arm_rule.arm_idx; + DEBUG("(" << arm_idx << ", " << arm_rule.pat_idx << "): " << arm_rule.m_rules); + root_node.populate_tree_from_rule( node.m_arms[arm_idx].m_code->span(), arm_idx, arm_rule.m_rules.data(), arm_rule.m_rules.size() ); + } + DEBUG("root_node = " << root_node); + root_node.simplify(); + root_node.propagate_default(); + DEBUG("root_node = " << root_node); + + // - Convert the above decision tree into MIR + DEBUG("- Emitting decision tree"); + DecisionTreeGen gen { builder, rule_blocks }; + builder.set_cur_block( first_cmp_block ); + gen.generate_tree_code( node.span(), root_node, node.m_value->m_res_type, mv$(match_val) ); + ASSERT_BUG(node.span(), !builder.block_active(), "Decision tree didn't terminate the final block"); +} // ---------------------------- // DecisionTreeNode @@ -1729,8 +1732,8 @@ void DecisionTreeNode::populate_tree_from_rule(const Span& sp, const PatternRule }), (Slice, //auto& be = GET_BRANCHES(m_branches, Slice); - // TODO: How to encode slice patterns in the DT? - // - SplitSlice throws a spanner in the works, and means that using the length isn't feasable + // TODO: How to encode slice patterns in the DT? Length check then sub-patterns. + // - SplitSlice throws a spanner in the works, and means that using the length isn't feasable in the long run TODO(sp, "Slice rules - " << rule); ), (Bool, -- cgit v1.2.3