From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1643) id 949243850230; Fri, 8 Jul 2022 07:31:28 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 949243850230 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Thomas Schwinge To: gcc-cvs@gcc.gnu.org Subject: [gcc/devel/rust/master] backend: initial support for matches on tuples X-Act-Checkin: gcc X-Git-Author: David Faust X-Git-Refname: refs/heads/devel/rust/master X-Git-Oldrev: 7784232540214b0fa500fa5682326f8841f170d5 X-Git-Newrev: b7c4aa942fa828038106105524af2c568acca7ac Message-Id: <20220708073128.949243850230@sourceware.org> Date: Fri, 8 Jul 2022 07:31:28 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 08 Jul 2022 07:31:28 -0000 https://gcc.gnu.org/g:b7c4aa942fa828038106105524af2c568acca7ac commit b7c4aa942fa828038106105524af2c568acca7ac Author: David Faust Date: Thu Jul 7 11:41:54 2022 -0700 backend: initial support for matches on tuples This is a first take on compiling matches on more complex expressions, starting with tuples. The general idea is to first rearrange the match into a simpler form, in which only one element of the scrutinee tuple is examined at a time. The remaining elements are then checked by a new match in each arm. By repeating this process, we end up with a series of nested matches each checking one element of the original scrutinee, which is equivalent to the original match expression, and which lowers directly to SWITCH_EXPR tree nodes (since these can only switch on one thing). The resulting SWITCH_EXPRs may be messy, and unoptimal, but we can rely on later optimizations in GENERIC and GIMPLE to clean them up for us. Diff: --- gcc/rust/backend/rust-compile-expr.cc | 397 +++++++++++++++++++++ gcc/testsuite/rust/execute/torture/match_tuple1.rs | 41 +++ 2 files changed, 438 insertions(+) diff --git a/gcc/rust/backend/rust-compile-expr.cc b/gcc/rust/backend/rust-compile-expr.cc index 02015b1a7c2..3740c801d6f 100644 --- a/gcc/rust/backend/rust-compile-expr.cc +++ b/gcc/rust/backend/rust-compile-expr.cc @@ -181,6 +181,321 @@ CompileExpr::visit (HIR::DereferenceExpr &expr) known_valid, expr.get_locus ()); } +// Helper for sort_tuple_patterns. +// Determine whether Patterns a and b are really the same pattern. +// FIXME: This is a nasty hack to avoid properly implementing a comparison +// for Patterns, which we really probably do want at some point. +static bool +patterns_mergeable (HIR::Pattern *a, HIR::Pattern *b) +{ + if (!a || !b) + return false; + + HIR::Pattern::PatternType pat_type = a->get_pattern_type (); + if (b->get_pattern_type () != pat_type) + return false; + + switch (pat_type) + { + case HIR::Pattern::PatternType::PATH: { + // FIXME: this is far too naive + HIR::PathPattern &aref = *static_cast (a); + HIR::PathPattern &bref = *static_cast (b); + if (aref.get_num_segments () != bref.get_num_segments ()) + return false; + + const auto &asegs = aref.get_segments (); + const auto &bsegs = bref.get_segments (); + for (size_t i = 0; i < asegs.size (); i++) + { + if (asegs[i].as_string () != bsegs[i].as_string ()) + return false; + } + return true; + } + break; + case HIR::Pattern::PatternType::LITERAL: { + HIR::LiteralPattern &aref = *static_cast (a); + HIR::LiteralPattern &bref = *static_cast (b); + return aref.get_literal ().is_equal (bref.get_literal ()); + } + break; + case HIR::Pattern::PatternType::IDENTIFIER: { + // TODO + } + break; + case HIR::Pattern::PatternType::WILDCARD: + return true; + break; + + // TODO + + default:; + } + return false; +} + +// A little container for rearranging the patterns and cases in a match +// expression while simplifying. +struct PatternMerge +{ + std::unique_ptr wildcard; + std::vector> heads; + std::vector> cases; +}; + +// Helper for simplify_tuple_match. +// For each tuple pattern in a given match, pull out the first elt of the +// tuple and construct a new MatchCase with the remaining tuple elts as the +// pattern. Return a mapping from each _unique_ first tuple element to a +// vec of cases for a new match. +// +// FIXME: This used to be a std::map>, but it doesn't +// actually work like we want - the Pattern includes an HIR ID, which is unique +// per Pattern object. This means we don't have a good means for comparing +// Patterns. It would probably be best to actually implement a means of +// properly comparing patterns, and then use an actual map. +// +static struct PatternMerge +sort_tuple_patterns (HIR::MatchExpr &expr) +{ + rust_assert (expr.get_scrutinee_expr ()->get_expression_type () + == HIR::Expr::ExprType::Tuple); + + struct PatternMerge result; + result.wildcard = nullptr; + result.heads = std::vector> (); + result.cases = std::vector> (); + + for (auto &match_case : expr.get_match_cases ()) + { + HIR::MatchArm &case_arm = match_case.get_arm (); + + // FIXME: Note we are only dealing with the first pattern in the arm. + // The patterns vector in the arm might hold many patterns, which are the + // patterns separated by the '|' token. Rustc abstracts these as "Or" + // patterns, and part of its simplification process is to get rid of them. + // We should get rid of the ORs too, maybe here or earlier than here? + auto pat = case_arm.get_patterns ()[0]->clone_pattern (); + + // Record wildcards so we can add them in inner matches. + if (pat->get_pattern_type () == HIR::Pattern::PatternType::WILDCARD) + { + // The *whole* pattern is a wild card (_). + result.wildcard + = std::unique_ptr (new HIR::MatchCase (match_case)); + continue; + } + + rust_assert (pat->get_pattern_type () + == HIR::Pattern::PatternType::TUPLE); + + auto ref = *static_cast (pat.get ()); + + rust_assert (ref.has_tuple_pattern_items ()); + + auto items + = HIR::TuplePattern (ref).get_items ()->clone_tuple_pattern_items (); + if (items->get_pattern_type () + == HIR::TuplePatternItems::TuplePatternItemType::MULTIPLE) + { + auto items_ref + = *static_cast (items.get ()); + + // Pop the first pattern out + auto patterns = std::vector> (); + auto first = items_ref.get_patterns ()[0]->clone_pattern (); + for (auto p = items_ref.get_patterns ().begin () + 1; + p != items_ref.get_patterns ().end (); p++) + { + patterns.push_back ((*p)->clone_pattern ()); + } + + // if there is only one pattern left, don't make a tuple out of it + std::unique_ptr result_pattern; + if (patterns.size () == 1) + { + result_pattern = std::move (patterns[0]); + } + else + { + auto new_items = std::unique_ptr ( + new HIR::TuplePatternItemsMultiple (std::move (patterns))); + + // Construct a TuplePattern from the rest of the patterns + result_pattern = std::unique_ptr ( + new HIR::TuplePattern (ref.get_pattern_mappings (), + std::move (new_items), + ref.get_locus ())); + } + + // I don't know why we need to make foo separately here but + // using the { new_tuple } syntax in new_arm constructor does not + // compile. + auto foo = std::vector> (); + foo.emplace_back (std::move (result_pattern)); + HIR::MatchArm new_arm (std::move (foo), Location (), nullptr, + AST::AttrVec ()); + + HIR::MatchCase new_case (match_case.get_mappings (), new_arm, + match_case.get_expr ()->clone_expr ()); + + bool pushed = false; + for (size_t i = 0; i < result.heads.size (); i++) + { + if (patterns_mergeable (result.heads[i].get (), first.get ())) + { + result.cases[i].push_back (new_case); + pushed = true; + } + } + + if (!pushed) + { + result.heads.push_back (std::move (first)); + result.cases.push_back ({new_case}); + } + } + else /* TuplePatternItemType::RANGED */ + { + // FIXME + gcc_unreachable (); + } + } + + return result; +} + +// Helper for CompileExpr::visit (HIR::MatchExpr). +// Given a MatchExpr where the scrutinee is some kind of tuple, build an +// equivalent match where only one element of the tuple is examined at a time. +// This resulting match can then be lowered to a SWITCH_EXPR tree directly. +// +// The approach is as follows: +// 1. Split the scrutinee and each pattern into the first (head) and the +// rest (tail). +// 2. Build a mapping of unique pattern heads to the cases (tail and expr) +// that shared that pattern head in the original match. +// (This is the job of sort_tuple_patterns ()). +// 3. For each unique pattern head, build a new MatchCase where the pattern +// is the unique head, and the expression is a new match where: +// - The scrutinee is the tail of the original scrutinee +// - The cases are are those built by the mapping in step 2, i.e. the +// tails of the patterns and the corresponing expressions from the +// original match expression. +// 4. Do this recursively for each inner match, until there is nothing more +// to simplify. +// 5. Build the resulting match which scrutinizes the head of the original +// scrutinee, using the cases built in step 3. +static HIR::MatchExpr +simplify_tuple_match (HIR::MatchExpr &expr) +{ + if (expr.get_scrutinee_expr ()->get_expression_type () + != HIR::Expr::ExprType::Tuple) + return expr; + + auto ref = *static_cast (expr.get_scrutinee_expr ().get ()); + + auto &tail = ref.get_tuple_elems (); + rust_assert (tail.size () > 1); + + auto head = std::move (tail[0]); + tail.erase (tail.begin (), tail.begin () + 1); + + // e.g. + // match (tupA, tupB, tupC) { + // (a1, b1, c1) => { blk1 }, + // (a2, b2, c2) => { blk2 }, + // (a1, b3, c3) => { blk3 }, + // } + // tail = (tupB, tupC) + // head = tupA + + // Make sure the tail is only a tuple if it consists of at least 2 elements. + std::unique_ptr remaining; + if (tail.size () == 1) + remaining = std::move (tail[0]); + else + remaining = std::unique_ptr ( + new HIR::TupleExpr (ref.get_mappings (), std::move (tail), + AST::AttrVec (), ref.get_outer_attrs (), + ref.get_locus ())); + + // e.g. + // a1 -> [(b1, c1) => { blk1 }, + // (b3, c3) => { blk3 }] + // a2 -> [(b2, c2) => { blk2 }] + struct PatternMerge map = sort_tuple_patterns (expr); + + std::vector cases; + // Construct the inner match for each unique first elt of the tuple + // patterns + for (size_t i = 0; i < map.heads.size (); i++) + { + auto inner_match_cases = map.cases[i]; + + // If there is a wildcard at the outer match level, then need to + // propegate the wildcard case into *every* inner match. + // FIXME: It is probably not correct to add this unconditionally, what if + // we have a pattern like (a, _, c)? Then there is already a wildcard in + // the inner matches, and having two will cause two 'default:' blocks + // which is an error. + if (map.wildcard != nullptr) + { + inner_match_cases.push_back (*(map.wildcard.get ())); + } + + // match (tupB, tupC) { + // (b1, c1) => { blk1 }, + // (b3, c3) => { blk3 } + // } + HIR::MatchExpr inner_match (expr.get_mappings (), + remaining->clone_expr (), inner_match_cases, + AST::AttrVec (), expr.get_outer_attrs (), + expr.get_locus ()); + + inner_match = simplify_tuple_match (inner_match); + + auto outer_arm_pat = std::vector> (); + outer_arm_pat.emplace_back (map.heads[i]->clone_pattern ()); + + HIR::MatchArm outer_arm (std::move (outer_arm_pat), expr.get_locus ()); + + // Need to move the inner match to the heap and put it in a unique_ptr to + // build the actual match case of the outer expression + // auto inner_expr = std::unique_ptr (new HIR::MatchExpr + // (inner_match)); + auto inner_expr = inner_match.clone_expr (); + + // a1 => match (tupB, tupC) { ... } + HIR::MatchCase outer_case (expr.get_mappings (), outer_arm, + std::move (inner_expr)); + + cases.push_back (outer_case); + } + + // If there was a wildcard, make sure to include it at the outer match level + // too. + if (map.wildcard != nullptr) + { + cases.push_back (*(map.wildcard.get ())); + } + + // match tupA { + // a1 => match (tupB, tupC) { + // (b1, c1) => { blk1 }, + // (b3, c3) => { blk3 } + // } + // a2 => match (tupB, tupC) { + // (b2, c2) => { blk2 } + // } + // } + HIR::MatchExpr outer_match (expr.get_mappings (), std::move (head), cases, + AST::AttrVec (), expr.get_outer_attrs (), + expr.get_locus ()); + + return outer_match; +} // Helper for CompileExpr::visit (HIR::MatchExpr). // Check that the scrutinee of EXPR is a valid kind of expression to match on. @@ -315,6 +630,88 @@ CompileExpr::visit (HIR::MatchExpr &expr) scrutinee_first_record_expr, 0, expr.get_scrutinee_expr ()->get_locus ()); } + else if (scrutinee_kind == TyTy::TypeKind::TUPLE) + { + // match on tuple becomes a series of nested switches, with one level + // for each element of the tuple from left to right. + auto exprtype = expr.get_scrutinee_expr ()->get_expression_type (); + switch (exprtype) + { + case HIR::Expr::ExprType::Tuple: { + // Build an equivalent expression which is nicer to lower. + HIR::MatchExpr outer_match = simplify_tuple_match (expr); + + // We've rearranged the match into something that lowers better + // to GENERIC trees. + // For actually doing the lowering we need to compile the match + // we've just made. But we're half-way through compiling the + // original one. + // ... + // For now, let's just replace the original with the rearranged one + // we just made, and compile that instead. What could go wrong? :) + // + // FIXME: What about when we decide a temporary is needed above? + // We might have already pushed a statement for it that + // we no longer need. Probably need to rearrange the order + // of these steps. + expr = outer_match; + + scrutinee_kind = check_match_scrutinee (expr, ctx); + if (scrutinee_kind == TyTy::TypeKind::ERROR) + { + translated = error_mark_node; + return; + } + + // Now compile the scrutinee of the simplified match. + // FIXME: this part is duplicated from above. + match_scrutinee_expr + = CompileExpr::Compile (expr.get_scrutinee_expr ().get (), ctx); + + if (TyTy::is_primitive_type_kind (scrutinee_kind)) + { + match_scrutinee_expr_qualifier_expr = match_scrutinee_expr; + } + else if (scrutinee_kind == TyTy::TypeKind::ADT) + { + // need to access qualifier the field, if we use QUAL_UNION_TYPE + // this would be DECL_QUALIFIER i think. For now this will just + // access the first record field and its respective qualifier + // because it will always be set because this is all a big + // special union + tree scrutinee_first_record_expr + = ctx->get_backend ()->struct_field_expression ( + match_scrutinee_expr, 0, + expr.get_scrutinee_expr ()->get_locus ()); + match_scrutinee_expr_qualifier_expr + = ctx->get_backend ()->struct_field_expression ( + scrutinee_first_record_expr, 0, + expr.get_scrutinee_expr ()->get_locus ()); + } + else + { + // FIXME: There are other cases, but it better not be a Tuple + gcc_unreachable (); + } + } + break; + + case HIR::Expr::ExprType::Ident: { + // FIXME + gcc_unreachable (); + } + break; + + case HIR::Expr::ExprType::Path: { + // FIXME + gcc_unreachable (); + } + break; + + default: + gcc_unreachable (); + } + } else { // FIXME: match on other types of expressions not yet implemented. diff --git a/gcc/testsuite/rust/execute/torture/match_tuple1.rs b/gcc/testsuite/rust/execute/torture/match_tuple1.rs new file mode 100644 index 00000000000..18740628912 --- /dev/null +++ b/gcc/testsuite/rust/execute/torture/match_tuple1.rs @@ -0,0 +1,41 @@ +// { dg-output "x:15\ny:20\n" } + +extern "C" { + fn printf(s: *const i8, ...); +} + +enum Foo { + A, + B, +} + +fn inspect(f: Foo, g: u8) -> i32 { + match (f, g) { + (Foo::A, 1) => { + return 5; + } + + (Foo::A, 2) => { + return 10; + } + + (Foo::B, 2) => { + return 15; + } + + _ => { + return 20; + } + } + return 25; +} + +fn main () -> i32 { + let x = inspect (Foo::B, 2); + let y = inspect (Foo::B, 1); + + printf ("x:%d\n" as *const str as *const i8, x); + printf ("y:%d\n" as *const str as *const i8, y); + + y - x - 5 +}